HDU5394 Bomb

题目：http://acm.hdu.edu.cn/showproblem.php?pid=5934

There are

N

InputFirst line contains an integer $T$ OutputFor every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the minimum cost.Sample Input

Sample Output

Case #1: 15

题意：有n个炸弹，每个炸弹放在(x, y)这个位置，它能炸的范围是以 r 为半径的圆，手动引爆这颗炸弹所需代价是c，当一个炸弹爆炸时，

在它爆炸范围内的所有炸弹都将被它引爆，让求把所有的炸弹都引爆，所需的最少代价是多少？

建立单向图，然后缩点，每个点的权值都为它所在联通块的权值的小的那个，然后找到所有入度为0的点，将他们的权值加起来就是结果；

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define met(a, b) memset(a, b, sizeof(a))
 4 typedef long long LL;
 5 const int N=1100;
 6 const int INF=0x3f3f3f3f;
 7 const double eps=1e-10;
 8 
 9 struct node{
10     LL x,y,r;
11 } a[N];
12 
13 int n,w[N],Min[N],dfn[N],low[N],vis[N];
14 int Belong[N],Blocks,Stack[N],Top,Time,ind[N];
15 vector<int> G[N];
16 
17 void Init()
18 {
19     for(int i=0; i<=n; i++) G[i].clear();
20     met(Min, INF); met(ind, 0);
21     met(dfn, 0); met(low, 0);
22     met(Stack, 0); met(vis, 0);
23     met(Belong, 0);
24     Blocks =Top=Time = 0;
25 }
26 
27 void Tajarn(int u)
28 {
29     low[u] = dfn[u] = ++Time;
30     Stack[Top++] = u;
31     vis[u] = 1;
32     int v;
33     for(int i=0;i<G[u].size();i++)
34     {
35         v=G[u][i];
36         if(!dfn[v])
37         {
38             Tajarn(v);
39             low[u]=min(low[u],low[v]);
40         }
41         else if(vis[v]) low[u]=min(low[u],dfn[v]);
42     }
43 
44     if(low[u]==dfn[u])
45     {
46         ++Blocks;
47         do
48         {
49             v = Stack[--Top];
50             Belong[v] = Blocks;
51             vis[v] = 0;
52         }while(u!=v);
53     }
54 }
55 
56 
57 int main()
58 {
59     int T, t = 1;
60     scanf("%d", &T);
61     while(T --)
62     {
63         scanf("%d", &n);
64         Init();
65         for(int i=1;i<=n;i++) scanf("%I64d%I64d%I64d%d",&a[i].x,&a[i].y,&a[i].r,&w[i]);
66         for(int i=1; i<=n; i++)
67         {
68             for(int j=1; j<=n; j++)
69             {
70                 LL d = (a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y);
71                 if(a[i].r*a[i].r>=d) G[i].push_back(j);
72             }
73         }
74 
75         for(int i=1;i<=n;i++) if(!dfn[i]) Tajarn(i);
76         for(int i=1;i<=n;i++)
77         {
78             for(int j=0;j<G[i].size();j++)
79             {
80                 int x = G[i][j];
81                 int u = Belong[i], v = Belong[x];
82                 if(u != v) ind[v] ++;
83                 Min[u] = min(Min[u], w[i]);
84                 Min[v] = min(Min[v], w[x]);
85             }
86         }
87 
88         int ans = 0;
89         for(int i=1;i<=Blocks;i++) if(ind[i]==0) ans+=Min[i];
90         
91         printf("Case #%d: %d
", t++, ans);
92     }
93     return 0;
94 }

View Code

2018-09-10 16:58:27