2016CCPC杭州现场赛 B-Bomb /// tarjan缩点

题目大意：

给定n个爆破点的信息 x y r w

表示爆破点位置为 (x,y) 爆破范围是以位置为圆心半径为r的圆引爆这个点的代价为w

引爆某个点时其他位置在该爆破范围内的爆破点也会被引爆

求引爆所有爆破点的最小的爆破代价

这道题跟上一篇的 OJ 22833（POJ 2186）差不多

那题是缩点再计算出度这题是缩点再计算入度

以爆破关系建图即若引爆 i 点能使 j 点被引爆那么连一条 i 到 j 的边

若存在点 k 的位置被包含在点 j 的爆破范围内，点 j 的位置被包含在点 i 的爆破范围内，但点 k 的位置不被包含在点 i 的爆破范围内

此时若引爆 i 点那么 j 点会被引爆，而 j 点被引爆 k 点也会被引爆，即爆破存在传递性

所以求完这个图的强联通分量并缩点后此时引爆这个图的里一个强联通分量

那么这个强联通分量能到达的其他强联通分量也会被引爆

又因为一个强联通分量内任意两点能互达所以引爆一个强联通分量只需要引爆它内部的其中一个点

那么引爆一个强联通分量应该贪心地选择它内部爆破代价最小的那个点

所以此时需要引爆的就是那些入度为0的强联通分量内爆破代价最小的点（由它们开始发生连环引爆）（图内的独立点入度也为0）

#include <stdio.h>

#include <cstring>

#include <algorithm>

#include <stack>

#define LL long long

#define INF 0x3f3f3f3f

using namespace std;

const int N=;

struct EDGE { int to, nt; }e[N*N];

int head[N], tot;

int dfn[N], low[N], ind;

int col[N], id;

bool vis[N];

stack <int> s;

int n, m, du[N];

LL x[N], y[N], r[N];

LL w[N], val[N];

void init() {

    while(!s.empty()) s.pop();

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

        head[i]=dfn[i]=low[i]=col[i]=-;

        vis[i]=du[i]=; val[i]=INF;

    }

    tot=ind=id=;

}

void addE(int u,int v) {

    e[tot].to=v;

    e[tot].nt=head[u];

    head[u]=tot++;

}

void tarjan(int u) {

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

    s.push(u); vis[u]=;

    for(int i=head[u];i!=-;i=e[i].nt) {

        int v=e[i].to;

        if(dfn[v]==-) {

            tarjan(v);

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

        }

        else if(vis[v])

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

    }

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

        col[u]=++id;

        vis[u]=;

        while(s.top()!=u) {

            col[s.top()]=id;

            vis[s.top()]=;

            s.pop();

        } s.pop();

    }

}

bool uni(int i,int j) {

    LL dis=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);

    if(dis<=r[i]*r[i]) return ;

    return ;

}

int main()

{

    int t, tcase=;

    scanf("%d",&t);

    while(t--) {

        scanf("%d",&n);

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

            scanf("%lld%lld%lld%lld",&x[i],&y[i],&r[i],&w[i]);

        init();

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

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

                if(uni(i,j)) addE(i,j); // j在i的爆破范围内 连i->j

                if(uni(j,i)) addE(j,i); // i在j的爆破范围内 连j->i

            }

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

            if(dfn[i]==-) tarjan(i);

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

            val[col[i]]=min(val[col[i]],w[i]);

            // 颜色相同说明在同个强联通分量内

            // 保存这个强联通分量内爆破代价最小的点

            for(int j=head[i];j!=-;j=e[j].nt)

                if(col[e[j].to]!=col[i])

                    du[col[e[j].to]]++; // 计算各个强联通分量的入度

        }

        LL ans=0LL;

        for(int i=;i<=id;i++)

            if(du[i]==) ans+=val[i]; // 入度为0 引爆

        printf("Case #%d: %lld\n",++tcase,ans);

    }

    return ;

}

巴特西

2016CCPC杭州现场赛 B-Bomb /// tarjan缩点

最新文章

热门文章