HDU5934 Bomb(2016杭州CCPC第二题)（强连通缩点）

Bomb

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

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

Sample Output

Case #1: 15

Source

2016年中国大学生程序设计竞赛（杭州）

【总结】感觉自己智商就是一坨屎，当时在杭州比赛的时候，看到这道题，就想到了强连通分量，但我想的方向错了，我一直想着把一些互相可以到达的点缩成一个点或者找一棵树的根，却没有想到从缩点后点的入度下手，真是亏了我前段时间刷了好多强连通的题。哎还是刷题太少，思路太狭窄而且比赛临场经验不足。真的很遗憾，我们当时是铁牌第一，我刚才照着模板敲了一下就过了，要是当时想到入度，就可以拿铜牌了。是该总结一下了，确实不能盲目刷题，还是要总结体型，拓展思路，不能再留下遗憾了。下面附上两个星期前就该A掉的代码。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#define inf 0x3f3f3f3f
#define met(a,b) memset(a,b,sizeof a)
typedef long long ll;
using namespace std;
const int N = 1005;
const int M = 24005;
int vis[N],dfn[N],low[N],head[N],stack1[N],num[N],in[N];
ll cost[N];
int n,m,tot,son,maxn,tim,top,cut;
ll ans;
struct EDG{int to,next;}edg[N*N];
struct node{ll x,y,r,c;}a[N];
bool cmp(node f,node g){return f.c<g.c;}
void add(int u,int v){
    edg[tot].to=v;edg[tot].next=head[u];head[u]=tot++;
}
void init(){
    met(head,-1);
    tot=tim=top=cut=0;
    met(vis,0);
    met(edg,0);
    met(in,0);
    met(cost,inf);
    met(stack1,0);met(num,0);met(dfn,0);met(low,0);
}
void Tarjan(int u) {
    int v;
    low[u] = dfn[u] = ++tim;
    stack1[top++] = u;
    vis[u] = 1;
    for(int e = head[u]; e != -1; e = edg[e].next){
        v = edg[e].to;
        if(!dfn[v]){
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        }else if(vis[v]){
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]){
        cut++;
        do{
            v = stack1[--top];
            num[v] = cut;
            cost[cut]=min(cost[cut],a[v].c);
            vis[v] = 0;
        }while(u != v);
    }
}
int main() {
    int T;
    scanf("%d",&T);
    for(int t=1;t<=T;t++){
        init();
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%lld%lld%lld%lld",&a[i].x,&a[i].y,&a[i].r,&a[i].c);
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==j)continue;
                if((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)<=a[i].r*a[i].r){
                    add(i,j);
                }
            }
        }
        for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);
        for(int i=1; i<=n; i++) {
            for(int j=head[i]; j!=-1; j=edg[j].next) {
                int v=edg[j].to;
                if(num[i]!=num[v])in[num[v]]++;
            }
        }
        ans=0;
        for(int i=1;i<=cut;i++){
            if(!in[i])ans+=cost[i];
        }
        printf("Case #%d: %lld
",t,ans);
    }
    return 0;
}