[原创]HDU 5934 Bomb [强连通+点基]【图论】

2017-06-09 13:48:43 Tabris_ 阅读数：285

博客爬取于2020-06-14 22:40:01
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72956798

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

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1160 Accepted Submission(s): 392

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.

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

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.

Sample Input
1
5
0 0 1 5
1 1 1 6
0 1 1 7
3 0 2 10
5 0 1 4

Sample Output
Case #1: 15

Source
2016年中国大学生程序设计竞赛（杭州）

————————————————————————————————————————
题目大意：
在一个直角坐标系上给你n个炸弹，这些炸弹可以被点燃引爆，或者被其他炸弹给连带。 点燃每个炸弹有一个花费，问引爆所有炸弹最少需要多少个。

解题思路：
首先根据能不能被连带引爆的关系建立有向图。

然后发现，只要有入度就一定能被其他节点引爆，没有入度就必须被点燃。

那么就将没有入度的点点燃加起来即可，

但是注意可能出现这样的情况，如果成环了， 那么一定要选择一个点，

所以我们可以缩点，然后新点的花费就是所有节点的花费中最小的。

缩点后后再统计没有入度花费总和即可

附本题代码
————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
# include<bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N   = 2333+7;
const int MOD = 1e9+7;
const int INF = (~(1<<31))>>1;

# define abs(x) ((x)>0?(x):-(x))

/****************************************************/
int x[N],y[N],r[N],c[N];

int dfn[N],low[N],color[N];
int vis[N],cnt,tot;
int cost[N],deg[N];
int mystack[N],len;
vector<int>G[N];

void dfs(int u){
    dfn[u]=low[u]=++cnt;
    vis[u]=1;
    mystack[++len]=u;
    int gz=G[u].size();
    for(int i=0,to;i<gz;i++){
        to=G[u][i];
        if(vis[to]==0)dfs(to);
        if(vis[to]==1)low[u]=min(low[u],low[to]);
    }
    if(dfn[u]==low[u]){
        ++tot;
        do{
            cost[tot]=min(cost[tot],c[mystack[len]]);
            color[mystack[len]]=tot;
            vis[mystack[len]]=2;
        }while(mystack[len--]!=u);
    }
}

LL dis(LL x){return x*x;}

bool judge(int i,int j){
    return dis(x[i]-x[j])+dis(y[i]-y[j])<=dis(r[i]);
}

int n;
int main(){
    int _,kcase=0;scanf("%d",&_);
    while(_--){
        tot=cnt=len=0;

        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d%d%d%d",&x[i],&y[i],&r[i],&c[i]);

        for(int i=1;i<=n;i++){cost[i]=INF,deg[i]=vis[i]=0;
            for(int j=1;j<=n;j++){
                if(i==j) continue;
                if(judge(i,j))G[i].push_back(j);
            }
        }

        for(int i=1;i<=n;i++) if(vis[i]==0) dfs(i);

        for(int i=1;i<=n;i++){
            int gz=G[i].size();
            for(int j=0,to;j<gz;j++){
                to=G[i][j];
                if(color[i]!=color[to])
                    deg[color[to]]++;
            }
        }

        int ans=0;
        for(int i=1;i<=tot;i++)
            if(deg[i]==0) ans+=cost[i];

        printf("Case #%d: %d\n",++kcase,ans);
        for(int i=1;i<=n;i++) G[i].clear();
    }
    return 0;
}