【題目描述】

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

【題目分析】
首先我們將問題轉化為圖論問題，我們按照能否引爆建圖，我們肯定想點的是最前面的雷，即入度為0的雷。
可是有可能有環怎么辦，我們將環用強連通分量縮成一個點，這樣就變成了DAG圖（有向無環圖），然后找到入度為0 的點，點燃里面耗費最少的（強連通分量內部點燃一個其他的都會被引爆）
$PS：$最好養成一個固定的做題習慣，比如下標是從0開始還是從1開始等。這里就因為前面從0開始后面從1開始wa了兩發。我覺得最好養成從1開始的習慣，雖然sort什么麻煩一點，但是容易理解，而且圖論中也不容易出錯，不容易越界等。

【AC代碼】

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<climits>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;typedef long long ll;
const int MAXN=1e3+5;
const int MAXM=2e6+5;
struct boom
{int x,y,r,c;
}Boom[MAXN];
struct node
{int v,next;
}Edge[MAXM];
int head[MAXN],tot;
int DFN[MAXN],LOW[MAXN];
int color[MAXN],cnt;
bool vis[MAXN];
int idx;
int stack[MAXN],top;
int In[MAXN];
int n,ans;void init()
{memset(head,0,sizeof(head)); tot=0;idx=0; memset(vis,0,sizeof(vis));memset(DFN,0,sizeof(DFN));memset(color,0,sizeof(color));cnt=0; top=0;memset(In,0,sizeof(In));
}bool Close(int i,int j)
{ll xi=Boom[i].x; ll yi=Boom[i].y;ll xj=Boom[j].x; ll yj=Boom[j].y;ll dis=Boom[i].r;return dis*dis>=(xi-xj)*(xi-xj)+(yi-yj)*(yi-yj);
}void AddEdge(int u,int v)
{tot++;Edge[tot].v=v; Edge[tot].next=head[u];head[u]=tot;
}void read()
{int u,v;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d%d%d",&Boom[i].x,&Boom[i].y,&Boom[i].r,&Boom[i].c);}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j) continue;if(Close(i,j)) AddEdge(i,j);}}
}void Trajan(int x)
{int v,tmp;DFN[x]=LOW[x]=++idx;stack[++top]=x; vis[x]=true;for(int i=head[x];i;i=Edge[i].next){v=Edge[i].v;if(!DFN[v]){Trajan(v);if(LOW[v]<LOW[x]) LOW[x]=LOW[v];}else if(vis[v] && LOW[v]<LOW[x]){LOW[x]=LOW[v];}}if(DFN[x]==LOW[x]){cnt++;do{tmp=stack[top--];vis[tmp]=false;color[tmp]=cnt;}while (tmp!=x);}
}void solve()
{int v;for(int i=1;i<=n;i++){if(!DFN[i])Trajan(i);}for(int i=1;i<=n;i++){for(int j=head[i];j;j=Edge[j].next){v=Edge[j].v;if(color[i]!=color[v])In[color[v]]++;}}ans=0;int minc;for(int i=1;i<=cnt;i++){if(!In[i]){minc=INT_MAX;for(int j=1;j<=n;j++){if(color[j]==i && Boom[j].c<minc){minc=Boom[j].c;}}ans+=minc;//printf("test: ans=%d minc=%d\n",ans,minc);}}
}int main()
{int T;scanf("%d",&T);for(int Case=1;Case<=T;Case++){init();read();solve();printf("Case #%d: %d\n",Case,ans);}return 0;
}