题意

在一平面内存在多颗炸弹，每颗炸弹有属性位置(x,y)，爆炸范围r，起爆花费c。

对于在起爆范围内的炸弹会连锁引爆，无花费。

求最小花费引爆所有炸弹。

思路

2016中国大学生程序设计竞赛的题目，图论题。

重现赛的时候队友用SPFA的思路WA了，就没有做下去。

寒假练习又看到了，重新思考了下，觉得有几条规律。

如果b在a的引爆范围，则添加a到b的有向边，可以得到一个有向图。

  • 对于入度为0的点是必须要起爆的。
  • 对于被上一条中的点引爆的点可以直接删去。
  • 对于出度为0的可以直接删去
  • 重复上一条，直到没有点被删除。

在删除确定的点后，剩下的显然都是环，在一个环内起爆一个最小花费点就可以了。

然而还是WA。

验证了下发现是漏了一个环指向另一个环的情况，被指向的环也是要被删除的。

于是对于一个环进行缩点，再删除出度为0的点。

这里题意原本大概是用Tarjan之类的算法求强连通分量。

但是本题比较特殊，所有的环都可以通过合并互相距离为1的点收缩为一个点。

例程

#include <cstdio>
#include <cstring>
#include <vector>
#include <bitset>
#include <algorithm>

using namespace std;

const int N = 1010;
typedef long long int64;

class Boom{
public:
    int r;
    int x;
    int y;
    int c;
    bool id;
    bool operator== (const Boom &a) const {
        return id == a.id;
    }
};
typedef vector<Boom>::iterator it;
vector<Boom> booms;
bitset<N> out[N];
bitset<N> in[N];
int n;

inline bool combo(Boom a,Boom b){
    if((a.r*(int64)a.r) >= 
            ((a.x-b.x)*(int64)(a.x-b.x) +
             (a.y-b.y)*(int64)(a.y-b.y)))
        return true;
    return false;
}

void shrink(int i){
    booms[i].id = false;
    for(int j=0;j<n;j++){
        if(booms[j].id && in[i][j]){
            in[i][j] = 0;
            out[j][i] = 0;
            if(out[j].none() && in[j].any()){
                shrink(j);
            }
        }
    }
}

int staining(int i){
    booms[i].id = false;
    int c = booms[i].c;
    for(int j=0;j<n;j++){
        if(booms[j].id && out[i][j]){
            c = min(c,staining(j));
        }
    }
    return c;
}

bool cmp(const Boom &a, const Boom &b) {
    if(a.id == b.id)return a.c < b.c;
    return a.id < b.id;
}

void merge(int a,int b) {
    booms[b].id = false;
    for(int i=0;i<n;i++){
        if(in[b][i]){
            out[i][b] = 0;
            out[i][a] = 1;
            in[a][i] = 1;
        }
        if(out[b][i]){
            in[i][b] = 0;
            in[i][a] = 1;
            out[a][i] = 1;
        }
    }
    in[a][a] = 0;
    out[a][a] = 0;
    for(int i=0;i<n;i++){
        if(booms[i].id){
            if(out[i][a] && out[a][i]){
                if(booms[i].c < booms[a].c)
                    merge(i,a);
                else
                    merge(a,i);
            }
        }
    }
}

int main(){
    int T,ans;
    Boom b;
    scanf("%d",&T);
    for(int t=1;t<=T;t++){
        booms.clear();
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d%d%d%d",&b.x,&b.y,&b.r,&b.c);
            b.id = true;
            booms.push_back(b);
            out[i].reset();
            in[i].reset();
        }
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(combo(booms[i],booms[j])){
                    out[i][j] = 1;
                    in[j][i] = 1;
                }
                if(combo(booms[j],booms[i])){
                    out[j][i] = 1;
                    in[i][j] = 1;
                }
            }
        }
        for(int i=0;i<n;i++){
            if(booms[i].id){
                for(int j=i+1;j<n;j++){
                    if(out[i][j] && out[j][i]){
                        if(booms[i].c < booms[j].c)
                            merge(i,j);
                        else
                            merge(j,i);
                    }
                }
            }
        }
        for(int i=0;i<n;i++) {
            in[i][i] = 0;
            out[i][i] = 0;
        }
        for(int i=0;i<n;i++){
            if(booms[i].id && out[i].none() && in[i].any()){
                shrink(i);
            }
        }
        ans = 0;
        for(int i=0;i<n;i++){
            if(booms[i].id){
                ans += staining(i);
            }
        }
        printf("Case #%d: %d\n",t,ans);
    }
    return 0;
}