题意：
给出n个炸弹的信息 ：坐标x , 坐标y , 爆炸半径 ， 成本：
如果一个炸弹被引爆那这个范围的都爆炸 ， 问最小的成本是多少？
题意：首先先来个n^2 暴力出某个炸弹爆炸波及的其他炸弹，用一条有向边来连接 ， 然后找到强连通分量 ，缩点 ， 就可以形成一张新的有向图 ， 那是不是就是所有没有点连接的点也就是入度为0 的点的权值和呀。想下某个炸弹只有出去的，没有进来的是不是必须得爆炸 。好这道题就可以ac了 ，
比赛的时候可能比较蒙蔽 ，强连通的性质没有想清楚 ， 想到是强连通 ， 但想的不够深入呀
/* *********************************************** Author :angon ************************************************ */ #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <stack> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; #define showtime fprintf(stderr,"time = %.15f ",clock() / (double)CLOCKS_PER_SEC) #define lld %I64d #define REP(i,k,n) for(int i=k;i<n;i++) #define REPP(i,k,n) for(int i=k;i<=n;i++) #define scan(d) scanf("%d",&d) #define scanl(d) scanf("%I64d",&d) #define scann(n,m) scanf("%d%d",&n,&m) #define scannl(n,m) scanf("%I64d%I64d",&n,&m) #define mst(a,k) memset(a,k,sizeof(a)) #define LL long long #define N 1005 #define mod 1000000007 inline int read(){int s=0;char ch=getchar();for(; ch<'0'||ch>'9'; ch=getchar());for(; ch>='0'&&ch<='9'; ch=getchar())s=s*10+ch-'0';return s;} struct Edge { int v,next; }edge[N*N]; int head[N],tot; int belong[N],Stack[N],inStack[N]; int low[N],dfn[N]; int scc,TimeN,top; int in[N]; LL x[N],y[N],r[N]; int c[N]; void addedge(int u,int v) { edge[tot].v=v; edge[tot].next=head[u]; head[u] = tot++; } void tarjan(int u) { dfn[u] = low[u] = ++TimeN; Stack[top++] = u; inStack[u] = 1; for(int i=head[u]; ~i; i=edge[i].next) { int v=edge[i].v; if(!dfn[v]) { tarjan(v); low[u] = min(low[u],low[v]); } else if(inStack[v]) low[u] = min(low[u],dfn[v]); } if(dfn[u]==low[u]) { int v; scc++; do { v = Stack[--top]; inStack[v] = 0; belong[v] = scc; }while(v!=u); } } void init() { mst(head,-1); tot=0; mst(inStack,0); mst(dfn,0); scc = top = TimeN = 0; mst(in,0); } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n; int t,cas=1; scan(t); while(t--) { scan(n); init(); REPP(i,1,n) { scannl(x[i],y[i]); scanl(r[i]); scan(c[i]); } REPP(i,1,n) { for(int j=1;j<=n;j++) { if(i==j) continue; if(sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j])) <= r[i]) addedge(i,j); } } REPP(u,1,n) if(!dfn[u]) tarjan(u); REPP(u,1,n) { for(int i=head[u]; ~i; i=edge[i].next) { int v=edge[i].v; if(belong[u]==belong[v]) continue; //out[belong[u]]++; in[belong[v]]++; } } int ans=0; REPP(i,1,scc) { if(in[i]==0) { int tmp = 1e5; for(int j = 1;j<=n;j++) { if(belong[j] == i) { //printf("%d belong %d ",j ,i); tmp = min(tmp,c[j]); } } ans += tmp; } } printf("Case #%d: %d ",cas++,ans);//max(r,c)); } return 0; }