HDU 5934 Bomb（炸弹）
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description - 题目描述
There are N bombs needing exploding.
Each bomb has three attributes: exploding radius ri, position (xi, yi) and lighting-cost ci which means you need to pay ci cost making it explode.
If a un-lighting bomb is in or on the border the exploding area of another exploding one, the un-lighting bomb also will explode.
Now you know the attributes of all bombs, please use the minimum cost to explode all bombs.
现有N颗炸弹急需引爆。每颗炸弹有三个属性：爆炸半径ri，炸弹位置(xi, yi)，还有起爆费用ci，即你需要花费ci才能引爆这个炸弹。如果一颗未引爆的炸弹在另一颗炸弹的爆炸半径边缘或者其中，则会被连锁引爆。此时你已得知所有炸弹的属性，用最小的花费引爆所有炸弹吧。
Input - 输入
First line contains an integer T, which indicates the number of test cases.
Every test case begins with an integers N, which indicates the numbers of bombs.
In the following N lines, the ith line contains four intergers xi, yi, ri and ci, indicating the coordinate of ith bomb is (xi,yi), exploding radius is ri and lighting-cost is ci.
Limits
- 1≤T≤20
- 1≤N≤1000
- −108≤xi,yi,ri≤108
- 1≤ci≤104
第一行为一个整数T，表示测试用例的数量。每个测试用例开头都有一个整数N，表示炸弹的数量。随后N行，第i行有四个整数xi，yi，ri，与ci，表示第i个炸弹的坐标(xi,yi)，爆炸半径ri与起爆费用ci。数据范围- 1≤T≤20- 1≤N≤1000- −10^8≤xi, yi, ri≤10^8- 1≤ci≤10^4
For 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.
对于每组测试用例，输出"Case #x: y"，x表示从1开始的用例编号，y为最小费用。
Sample Input - 输入样例
150 0 1 51 1 1 60 1 1 73 0 2 105 0 1 4
Sample Output - 输出样例
Case #1: 15
题解
Tarjan缩点
先根据每个炸弹的爆炸范围和坐标构造出一个有向图，然后再进行缩点。 入度为0的点则为需要引爆的点，将其费用相加即是结果。
代码 C++
1 #include2 #include 3 #define ll __int64 4 #define mx 1005 5 int n, c[mx]; 6 7 struct Edge{ 8 int to, nxt; 9 }edge[mx*mx];10 int head[mx], iE;11 void addEdge(int u, int v){12 edge[iE].to = v; edge[iE].nxt = head[u];13 head[u] = iE++;14 }15 16 struct Point{17 ll x, y, r;18 }data[mx];19 bool cmp(int i, int j){20 ll oo, rr;21 oo = (data[i].x - data[j].x)*(data[i].x - data[j].x) + (data[i].y - data[j].y)*(data[i].y - data[j].y);22 rr = data[i].r*data[i].r;23 return oo <= rr;24 }25 26 int stack[mx], inUS[mx], iS, ID[mx], fID[mx], iF, size[mx];27 void Tarjan(int now){28 fID[now] = ++iF;29 stack[++iS] = now; inUS[now] = 1;30 int u, v, i = iS, fIDold = fID[now];31 for (u = head[now]; ~u; u = edge[u].nxt){32 v = edge[u].to;33 ++size[ID[v]];34 if (inUS[v] == 0) Tarjan(v);35 if (~inUS[v]) fID[now] = std::min(fID[v], fID[now]);36 }37 if (fID[now] == fIDold){38 while (iS >= i){39 ID[stack[iS]] = now; inUS[stack[iS]] = -1;40 c[now] = std::min(c[stack[iS]], c[now]);41 --iS;42 }43 }44 }45 46 void read(){47 scanf("%d", &n);48 int i, j;49 for (i = 0; i < n; ++i){50 scanf("%I64d%I64d%I64d%d", &data[i].x, &data[i].y, &data[i].r, &c[i]);51 head[i] = -1; ID[i] = i; inUS[i] = 0;52 }53 iE = 0;54 for (i = 0; i < n; ++i){55 for (j = i + 1; j < n; ++j){56 if (cmp(i, j)) addEdge(i, j);57 if (cmp(j, i)) addEdge(j, i);58 }59 }60 61 iS = iF = 0;62 for (i = 0; i < n; ++i){63 if (inUS[i] == 0){ Tarjan(i); size[ID[i]] = 0; }64 }65 }66 67 int sum(){68 int i, opt = 0;69 for (i = 0; i < n; ++i){70 if (size[i] == 0) opt += c[ID[i]];71 }72 return opt;73 }74 75 int main(){76 int t, it, i;77 for (it = scanf("%d", &t); t; --t, ++it){78 read();79 printf("Case #%d: %d\n", it, sum());80 }81 return 0;82 }