HDU 5934 Bomb 【图论缩点】（2016年中国大学生程序设计竞赛（杭州））

Bomb

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

Problem Description

There are

Input

First line contains an integer

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年中国大学生程序设计竞赛（杭州）

Recommend

liuyiding   |   We have carefully selected several similar problems for you:  5943 5942 5941 5940 5939

Statistic | Submit | Discuss | Note

题目链接：

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

题目大意：

　　N个炸弹，坐标(x,y)，爆炸半径r，人为引爆的代价为c。

　　如果一个炸弹在已经爆炸的炸弹的爆炸半径内(上)，那么这个炸弹也会被引爆（连锁反应，不需要代价）

　　问至少多少代价可以把所有炸弹引爆。

题目思路：

　　【图论缩点】

　　如果A能引爆B那么A向B连一条边。

　　建完图之后用Tarjin或者Kosaraju强连通缩点。

　　缩完点之后的图是有向无环图。

　　再根据新的点连边，那些入度为0的点即为需要人为引爆的。统计代价即可。

  1 //
  2 //by coolxxx
  3 //#include<bits/stdc++.h>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<string>
  7 #include<iomanip>
  8 #include<map>
  9 #include<stack>
 10 #include<queue>
 11 #include<set>
 12 #include<bitset>
 13 #include<memory.h>
 14 #include<time.h>
 15 #include<stdio.h>
 16 #include<stdlib.h>
 17 #include<string.h>
 18 //#include<stdbool.h>
 19 #include<math.h>
 20 #pragma comment(linker,"/STACK:1024000000,1024000000")
 21 #define min(a,b) ((a)<(b)?(a):(b))
 22 #define max(a,b) ((a)>(b)?(a):(b))
 23 #define abs(a) ((a)>0?(a):(-(a)))
 24 #define lowbit(a) (a&(-a))
 25 #define sqr(a) ((a)*(a))
 26 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
 27 #define mem(a,b) memset(a,b,sizeof(a))
 28 #define eps (1e-8)
 29 #define J 10000
 30 #define mod 1000000007
 31 #define MAX 0x7f7f7f7f
 32 #define PI 3.14159265358979323
 33 #define N 1004
 34 #define M 1000004
 35 using namespace std;
 36 typedef long long LL;
 37 double anss;
 38 LL aans;
 39 int cas,cass;
 40 int n,m,lll,ans;
 41 int ll,sz;
 42 int fa[N],in[N],last[N],last1[N],num[N],cc[N];
 43 bool mark[N];
 44 struct Point
 45 {
 46     LL x,y,r;
 47     int c;
 48 }p[N];
 49 struct xxx
 50 {
 51     int next,to;
 52 }a[M],b[M];
 53 void add(int x,int y)
 54 {
 55     a[++lll].next=last[x];
 56     a[lll].to=y;
 57     last[x]=lll;
 58 }
 59 void link(int x,int y)
 60 {
 61     b[++ll].next=last1[x];
 62     b[ll].to=y;
 63     last1[x]=ll;
 64 }
 65 void dfs1(int now)
 66 {
 67     int i;
 68     mark[now]=1;
 69     for(i=last[now];i;i=a[i].next)
 70         if(!mark[a[i].to])
 71             dfs1(a[i].to);
 72     num[++sz]=now;
 73 }
 74 void dfs2(int now)
 75 {
 76     int i;
 77     mark[now]=1;
 78     fa[now]=m;
 79     cc[m]=min(cc[m],p[now].c);
 80     for(i=last1[now];i;i=b[i].next)
 81     {
 82         if(!mark[b[i].to])
 83             dfs2(b[i].to);
 84     }
 85 }
 86 void kosaraju()
 87 {
 88     int i;
 89     mem(mark,0);sz=0;m=0;
 90     for(i=1;i<=n;i++)
 91         if(!mark[i])
 92             dfs1(i);
 93     mem(mark,0);
 94     for(i=n;i;i--)
 95     {
 96         if(!mark[num[i]])
 97         {
 98             cc[++m]=MAX;
 99             dfs2(num[i]);
100         }
101     }
102 }
103 int main()
104 {
105     #ifndef ONLINE_JUDGEW
106 //    freopen("1.txt","r",stdin);
107 //    freopen("2.txt","w",stdout);
108     #endif
109     int i,j,k;
110     int x,y,z;
111 //    init();
112 //    for(scanf("%d",&cass);cass;cass--)
113     for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
114 //    while(~scanf("%s",s))
115 //    while(~scanf("%d%d",&n,&m))
116     {
117         printf("Case #%d: ",cass);
118         lll=0;ll=0;ans=0;
119         mem(in,0);mem(last,0);mem(last1,0);
120         scanf("%d",&n);
121         for(i=1;i<=n;i++)scanf("%lld%lld%lld%lld",&p[i].x,&p[i].y,&p[i].r,&p[i].c);
122         for(i=1;i<=n;i++)
123         {
124             for(j=1;j<=n;j++)
125             {
126                 if(i==j)continue;
127                 if(sqr(p[i].r)>=sqr(p[i].x-p[j].x)+sqr(p[i].y-p[j].y))
128                     add(i,j),link(j,i);
129             }
130         }
131         kosaraju();
132         for(i=1;i<=n;i++)
133         {
134             for(j=last[i];j;j=a[j].next)
135             {
136                 if(fa[a[j].to]==fa[i])continue;
137                 in[fa[a[j].to]]++;
138             }
139         }
140         for(i=1;i<=m;i++)
141             if(!in[i])
142                 ans+=cc[i];
143         printf("%d
",ans);
144     }
145     return 0;
146 }
147 /*
148 //
149 
150 //
151 */

View Code