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

- −10⁸≤xi,yi,ri≤10⁸

- 1≤ci≤10⁴

第一行为一个整数T，表示测试用例的数量。

每个测试用例开头都有一个整数N，表示炸弹的数量。

随后N行，第i行有四个整数xi，yi，ri，与ci，表示第i个炸弹的坐标(xi,yi)，爆炸半径ri与起爆费用ci。

数据范围

- ≤T≤

- ≤N≤

- −^≤xi, yi, ri≤^

- ≤ci≤^

Output - 输出

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 - 输入样例

Sample Output - 输出样例

Case #1: 15

题解

　　Tarjan缩点
　　先根据每个炸弹的爆炸范围和坐标构造出一个有向图，然后再进行缩点。
　　入度为0的点则为需要引爆的点，将其费用相加即是结果。

代码 C++

 #include <cstdio>

 #include <algorithm>

 #define ll __int64

 #define mx 1005

 int n, c[mx];

 struct Edge{

     int to, nxt;

 }edge[mx*mx];

 int head[mx], iE;

 void addEdge(int u, int v){

     edge[iE].to = v; edge[iE].nxt = head[u];

     head[u] = iE++;

 }

 struct Point{

     ll x, y, r;

 }data[mx];

 bool cmp(int i, int j){

     ll oo, rr;

     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);

     rr = data[i].r*data[i].r;

     return oo <= rr;

 }

 int stack[mx], inUS[mx], iS, ID[mx], fID[mx], iF, size[mx];

 void Tarjan(int now){

     fID[now] = ++iF;

     stack[++iS] = now; inUS[now] = ;

     int u, v, i = iS, fIDold = fID[now];

     for (u = head[now]; ~u; u = edge[u].nxt){

         v = edge[u].to;

         ++size[ID[v]];

         if (inUS[v] == ) Tarjan(v);

         if (~inUS[v]) fID[now] = std::min(fID[v], fID[now]);

     }

     if (fID[now] == fIDold){

         while (iS >= i){

             ID[stack[iS]] = now; inUS[stack[iS]] = -;

             c[now] = std::min(c[stack[iS]], c[now]);

             --iS;

         }

     }

 }

 void read(){

     scanf("%d", &n);

     int i, j;

     for (i = ; i < n; ++i){

         scanf("%I64d%I64d%I64d%d", &data[i].x, &data[i].y, &data[i].r, &c[i]);

         head[i] = -; ID[i] = i; inUS[i] = ;

     }

     iE = ;

     for (i = ; i < n; ++i){

         for (j = i + ; j < n; ++j){

             if (cmp(i, j)) addEdge(i, j);

             if (cmp(j, i)) addEdge(j, i);

         }

     }

     iS = iF = ;

     for (i = ; i < n; ++i){

         if (inUS[i] == ){ Tarjan(i); size[ID[i]] = ; }

     }

 }

 int sum(){

     int i, opt = ;

     for (i = ; i < n; ++i){

         if (size[i] == ) opt += c[ID[i]];

     }

     return opt;

 }

 int main(){

     int t, it, i;

     for (it = scanf("%d", &t); t; --t, ++it){

         read();

         printf("Case #%d: %d\n", it, sum());

     }

     return ;

 }

秒客网

HDU 5934 Bomb（炸弹）

HDU 5934 Bomb（炸弹）

相关文章