Bomb

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

Problem Description

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
 

Source

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

Recommend

liuyiding

先利用强连通分量缩点,这样图就不存在环了,然后再直接引入度为0的点就好

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 1e5;
const int INF = 1e9;
vector<int> G[maxn];
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
stack<int> S;

void dfs(int u)
{
    pre[u] = lowlink[u] = ++dfs_clock;
    S.push(u);
    for(int i=0;i < G[u].size();i++)
    {
        int v = G[u][i];
        if(!pre[v])
        {
            dfs(v);
            lowlink[u] = min(lowlink[u],lowlink[v]);

        }
        else if(!sccno[v])
        {
            lowlink[u] = min(lowlink[u],pre[v]);
        }
    }
    if(lowlink[u] == pre[u])
    {
        scc_cnt++;
        for(;;)
        {
            int x = S.top();
            S.pop();
            sccno[x] = scc_cnt;
            if(x==u) break;
        }
    }
}

void find_scc(int n)
{
    dfs_clock = scc_cnt = 0;
    memset(sccno,0,sizeof(sccno));
    memset(pre,0,sizeof(pre));
    for(int i = 0;i < n;i++)
    {
        if(!pre[i])
        {
            dfs(i);
        }
    }
}


int n;

ll x[1005];
ll y[1005];
ll r[1005];
ll c[1005];

ll getdis(int i,int j)
{
    return (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
}
ll in[maxn];
int T;
ll nto[maxn];
ll num[maxn];
int main()
{
//    freopen("data.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    scanf("%d",&T);
    int cas=0;
    while(T--)
    {
        cas++;
        cout <<"Case #"<<cas<<": ";
        scanf("%d",&n);

        memset(in,0,sizeof(in));
        memset(num,0,sizeof(num));
        for(int i=0;i<=n;i++)
        {
            nto[i]=INF;
            G[i].clear();
        }

        for(int i=0;i<n;i++)
        {
            scanf("%lld%lld%lld%lld",&x[i],&y[i],&r[i],&c[i]);
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(j==i) continue;
                if(r[i]*r[i]>=getdis(i,j))
                {
//                    cout << i<<"->"<<j<<endl;
                    G[i].push_back(j);
                }
                if(r[j]*r[j]>=getdis(i,j))
                {
//                    cout << j <<"->"<< i <<endl;
                    G[j].push_back(i);
                }
            }
        }
        find_scc(n);

        for(int i=0;i<n;i++)
        {
            num[sccno[i]]++;
            nto[ sccno[i] ] = min(nto[ sccno[i] ],c[i]);
        }

        ll ans =0 ;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<G[i].size();j++)
            {
                if(sccno[G[i][j]]!=sccno[i])
                    in[ sccno[G[i][j]] ]++;
            }
        }

        for(int i=1;i<=scc_cnt;i++)
        {
            if(in[i]==0)
            {
                ans += nto[i];
            }
        }
        cout << ans<<endl;
    }
    return 0;
}