题目

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

题解

平面内有一些炸弹,每个炸弹有一定得爆炸范围,炸弹爆炸时会引爆爆炸范围内的炸弹,花费最少的能量使所有炸弹被引爆

显然,是一道有向图的题目

作图如下:

转为有向图关系有:

节点被分为多个连通分量.
如果两个点属于一个 强连通分量 那么可以将他们看作一个点(用最小点燃能量作为代价)
然后将新的图建成 有向图
此时,图中 不存在强连通的结点(无环) 因此只需要找到 入度为0 的点点燃即可
(无环,所以从任何入度不为0的点往回走,必然终止于一个入度为0的点)

那么任务也即:

强连通分量缩点
建有向图图
查找所有入度为 0 的点

强连通分量缩点 套用模板即可

处理时,要注意坐标可能会溢出 int
因此使用 long long 存储坐标

代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;


/*
    * Tarjan算法
    * 复杂度O(N+M)
*/
const int MAXN = 1005;//点数 
const int MAXM = 2*MAXN*MAXN;//边数 
struct Edge {
    int to,next;
}edge[MAXM];

int head[MAXN],tot;
int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~scc 
int Index,top;
int scc;//强连通分量的个数 

bool Instack[MAXN];
int num[MAXN];//各个强连通分量包含点的个数，数组编号1~scc 
              //num数组不一定需要，结合实际情况 

void addedge(int u,int v) {
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}

void Tarjan(int u) {
    int v;
    Low[u] = DFN[u] = ++Index;
    Stack[top++] = u;
    Instack[u] = true;
    for(int i = head[u];i != -1;i = edge[i].next) {
        v = edge[i].to;
        if(!DFN[v]) {
            Tarjan(v);
            if(Low[u] > Low[v])
                Low[u] = Low[v];
        } else if(Instack[v] && Low[u] > DFN[v])
            Low[u] = DFN[v];
    }  
    
    if(Low[u] == DFN[u]) {
        scc++;
        do {
            v = Stack[--top];
            Instack[v] = false;
            Belong[v] = scc;
            num[scc]++;
        } while(v != u);
    }
}

void solve(int N) {
    memset(DFN,0,sizeof(DFN));
    memset(Instack,false,sizeof(Instack));
    memset(num,0,sizeof(num));
    Index = scc = top = 0;
    for(int i = 1;i <= N;i++)
        if(!DFN[i])
            Tarjan(i);
}

void init() {
    tot = 0;
    memset(head,-1,sizeof(head));
}


struct Point {
    long long x,y;
    long long r;
    int w;
    Point(long long a = 0,long long b = 0,long long c = 0,int d = 0):x(a),y(b),r(c),w(d) {}
    static long long distanceSqure(const Point &a,const Point &b) {
        return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
    }
};
Point p[MAXN];

int Min[MAXN];

int main() {
    //freopen("in.txt","r",stdin);
    cin.tie(0);
    cin.sync_with_stdio(false);

    int T;
    cin >> T;
    int kase = 1;
    while(T--) {

        int n;
        cin >> n;
        for(int i = 1;i <= n;i++) {
            Point &t = p[i];
            cin >> t.x >> t.y >> t.r >> t.w;
        }
        
        init();

        //建图
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++)
                if(i != j) {
                    long long dis = Point::distanceSqure(p[i],p[j]);
                    if((long long)p[i].r * (long long)p[i].r - dis >= 0)
                        addedge(i,j);
                }

        //Tarjan + 缩点
        solve(n);

        //寻找入度为0的点
        memset(Instack,false,sizeof(Instack));

        for(int i = 1;i <= n;i++)
            for(int j = head[i];j != -1;j = edge[j].next)
                if(Belong[i] != Belong[edge[j].to])
                    Instack[Belong[edge[j].to]] = true;

        for(int i = 1;i <= scc;i++)
            Min[i] = 10005;

        for(int i = 1;i <= n;i++) {
            int tscc = Belong[i];
            Min[tscc] = min(Min[tscc],p[i].w);
        }

        int ans = 0;
        for(int i = 1;i <= scc;i++) {
            if(Instack[i] == false)
                ans += Min[i];
        }

        cout << "Case #" << kase++ << ": " << ans << endl;

    }
    return 0;
}

HDU 5934.Bomb(2016 CCPC 杭州 B)