[HDOJ5934]Bomb（强连通分量，缩点）

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

题意：有n个炸弹，爆炸范围和点燃花费给你，如果一个爆炸那么它爆炸范围内的炸弹也会爆炸。问让所有炸弹爆炸的最小花费。

遍历任意两个炸弹，如果i在j的爆炸范围内，则建一条有向边。缩完点以后找入度为0的点点燃就行了。

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 typedef struct Edge {

     int u;

     int v;

     int next;

     Edge() { next = -; }

 }Edge;

 typedef struct P {

     LL x, y, r;

     int c;

 }P;

 const int maxn = ;

 P p[maxn];

 int head[maxn], ecnt;

 Edge edge[maxn*maxn];

 int n, m;

 int bcnt, dindex;

 int dfn[maxn], low[maxn];

 int stk[maxn], top;

 int belong[maxn];

 bool instk[maxn];

 int ret[maxn];

 int in[maxn];

 void init() {

     memset(edge, , sizeof(edge));

     memset(head, -, sizeof(head));

     memset(instk, , sizeof(instk));

     memset(dfn, , sizeof(dfn));

     memset(low, , sizeof(low));

     memset(belong, , sizeof(belong));

     ecnt = top = bcnt = dindex = ;

 }

 void adde(int uu, int vv) {

     edge[ecnt].u = uu;

     edge[ecnt].v = vv;

     edge[ecnt].next = head[uu];

     head[uu] = ecnt++;

 }

 void tarjan(int u) {

     int v = u;

     dfn[u] = low[u] = ++dindex;

     stk[++top] = u;

     instk[u] = ;

     for(int i = head[u]; ~i; i=edge[i].next) {

         v = edge[i].v;

         if(!dfn[v]) {

             tarjan(v);

             low[u] = min(low[u], low[v]);

         }

         else if(instk[v]) low[u] = min(low[u], dfn[v]);

     }

     if(dfn[u] == low[u]) {

         bcnt++;

         do {

             v = stk[top--];

             instk[v] = ;

             belong[v] = bcnt;

         } while(v != u);

     }

 }

 LL dis(P a, P b) {

     LL l1 = a.x - b.x;

     LL l2 = a.y - b.y;

     return l1 * l1 + l2 * l2;

 }

 int main() {

     // freopen("in", "r", stdin);

     int T, _ = ;

     scanf("%d", &T);

     while(T--) {

         scanf("%d", &n);

         init();

         memset(in, , sizeof(in));

         for(int i = ; i <= n; i++) ret[i] = ;

         for(int i = ; i <= n; i++) {

             scanf("%I64d%I64d%I64d%d",&p[i].x,&p[i].y,&p[i].r,&p[i].c);

         }

         for(int i = ; i <= n; i++) {

             for(int j = ; j <= n; j++) {

                 if(i == j) continue;

                 LL d = dis(p[i], p[j]);

                 if(d <= (LL)p[i].r * p[i].r) adde(i, j);

             }

         }

         for(int i = ; i <= n; i++) {

             if(!dfn[i]) tarjan(i);

         }

         for(int i = ; i < ecnt; i++) {

             int u = edge[i].u, v = edge[i].v;

             if(belong[u] != belong[v]) in[belong[v]]++;

         }

         for(int i = ; i <= n; i++) {

             ret[belong[i]] = min(ret[belong[i]], p[i].c);

         }

         int tot = ;

         for(int i = ; i <= bcnt; i++) {

             if(!in[i]) tot += ret[i];

         }

         printf("Case #%d: ", _++);

         printf("%d\n", tot);

     }

     return ;

 }