题目大意：
给定n个爆破点的信息 x y r w
表示爆破点位置为 (x,y) 爆破范围是以位置为圆心 半径为r的圆 引爆这个点的代价为w
引爆某个点时 其他位置在该爆破范围内的爆破点也会被引爆
求引爆所有爆破点的最小的爆破代价
这道题跟 上一篇的 OJ 22833（POJ 2186） 差不多
那题是缩点再计算出度 这题是缩点再计算入度
以爆破关系建图 即若引爆 i 点能使 j 点被引爆 那么连一条 i 到 j 的边
若存在点 k 的位置被包含在点 j 的爆破范围内，点 j 的位置被包含在点 i 的爆破范围内，但点 k 的位置不被包含在点 i 的爆破范围内
此时若引爆 i 点 那么 j 点会被引爆，而 j 点被引爆 k 点也会被引爆，即爆破存在传递性
所以求完这个图的强联通分量并缩点后 此时引爆这个图的里一个强联通分量
那么这个强联通分量能到达的其他强联通分量也会被引爆
又因为一个强联通分量内任意两点能互达 所以引爆一个强联通分量只需要引爆它内部的其中一个点
那么引爆一个强联通分量 应该贪心地选择它内部爆破代价最小的那个点
所以此时需要引爆的就是那些 入度为0的强联通分量内爆破代价最小的点 （由它们开始发生连环引爆）（图内的独立点入度也为0）
#include <stdio.h> #include <cstring> #include <algorithm> #include <stack> #define LL long long #define INF 0x3f3f3f3f using namespace std; const int N=1005; struct EDGE { int to, nt; }e[N*N]; int head[N], tot; int dfn[N], low[N], ind; int col[N], id; bool vis[N]; stack <int> s; int n, m, du[N]; LL x[N], y[N], r[N]; LL w[N], val[N]; void init() { while(!s.empty()) s.pop(); for(int i=0;i<=n;i++) { head[i]=dfn[i]=low[i]=col[i]=-1; vis[i]=du[i]=0; val[i]=INF; } tot=ind=id=0; } void addE(int u,int v) { e[tot].to=v; e[tot].nt=head[u]; head[u]=tot++; } void tarjan(int u) { dfn[u]=low[u]=ind++; s.push(u); vis[u]=1; for(int i=head[u];i!=-1;i=e[i].nt) { int v=e[i].to; if(dfn[v]==-1) { tarjan(v); low[u]=min(low[u],low[v]); } else if(vis[v]) low[u]=min(low[u],low[v]); } if(dfn[u]==low[u]) { col[u]=++id; vis[u]=0; while(s.top()!=u) { col[s.top()]=id; vis[s.top()]=0; s.pop(); } s.pop(); } } bool uni(int i,int j) { LL dis=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]); if(dis<=r[i]*r[i]) return 1; return 0; } int main() { int t, tcase=0; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld%lld%lld%lld",&x[i],&y[i],&r[i],&w[i]); init(); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { if(uni(i,j)) addE(i,j); // j在i的爆破范围内 连i->j if(uni(j,i)) addE(j,i); // i在j的爆破范围内 连j->i } for(int i=1;i<=n;i++) if(dfn[i]==-1) tarjan(i); for(int i=1;i<=n;i++) { val[col[i]]=min(val[col[i]],w[i]); // 颜色相同说明在同个强联通分量内 // 保存这个强联通分量内爆破代价最小的点 for(int j=head[i];j!=-1;j=e[j].nt) if(col[e[j].to]!=col[i]) du[col[e[j].to]]++; // 计算各个强联通分量的入度 } LL ans=0LL; for(int i=1;i<=id;i++) if(du[i]==0) ans+=val[i]; // 入度为0 引爆 printf("Case #%d: %lld ",++tcase,ans); } return 0; }