tarjan 视频讲解

/**

 *      题目链接：https://vjudge.net/problem/HDU-5934

 * 题意：给你n个炸弹，引爆每个炸弹会有一定的花费。每个炸弹给出坐标x，y，半径r，引爆花费；

 * 引爆一个炸弹会把范围内的炸弹引爆，连锁反应。 现在想把所有炸弹引爆的最小花费。

 *

 * 解题思路：强连通缩点。根据a能够引爆b，可以在建一条a到b的单向边。如果是一个强连通（这一部分的图，

 * 任意两点都可以相互到达）那么就把这个强连通分量变成一个点，值最分量的最小值。这样图就变成有向无环图了。

 * 考虑到每个点的花费都是大于0的，所以引爆开始点最划算，即为入度为0的点。

 *

 * 前置技能 tarjan 缩点。

*/

#include <bits/stdc++.h>

using namespace std;

const int maxn=1000+10;

const int INF=2e9+1e8;

vector<int>E[maxn];

struct Point

{

    int x,y,r,cost;

}boom[maxn];

bool judge(Point a,Point b)

{

    if( 1ll*(a.x-b.x)*(a.x-b.x)+1ll*(a.y-b.y)*(a.y-b.y)<=1ll*a.r*a.r ) return true;

    return false;

}

int dfn[maxn],low[maxn],id,vis[maxn],ans,deg[maxn];

int num[maxn],cnt,cost[maxn];//对点进行重新编号，（数组num），按照联通分量进行编号

stack<int>S;

void init()

{

    id=cnt=0;

    memset(deg,0,sizeof(deg));

    memset(num,0,sizeof(num));

    memset(vis,0,sizeof(vis));

    memset(dfn,0,sizeof(dfn));

}

void tarjan(int x)

{

    low[x]=dfn[x]=++id;

    S.push(x);

    vis[x]=1;

    for(int i=0;i<(int)E[x].size();i++)

    {

        int to=E[x][i];

        if(!dfn[to])

        {

            tarjan(to);

            low[x]=min(low[x],low[to]);

        }

        else if(vis[to]) low[x]=min(low[x],dfn[to]);

    }

    if(low[x]==dfn[x])

    {

        int mincost=INF,in=0;

        cnt++;

        while(1)

        {

            int now=S.top();

            S.pop();

            vis[now]=0;

            num[now]=cnt;

            mincost=min(mincost,boom[now].cost);

            if(now==x) break;

        }

        cost[cnt]=mincost;

    }

}

int main()

{

    int T,cas=1;

    scanf("%d",&T);

    while(T--)

    {

        int n;

        scanf("%d",&n);

        init();

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

        {

            E[i].clear();

            scanf("%d%d%d%d",&boom[i].x,&boom[i].y,&boom[i].r,&boom[i].cost);

        }

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

        {

            for(int j=1;j<=n;j++)

            {

                if(i==j) continue;

                if(judge(boom[i],boom[j])) E[i].push_back(j);

            }

        }

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

            if(!dfn[i]) tarjan(i);

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

        {

            for(int j=0;j<(int)E[i].size();j++)

            {

                int to=E[i][j];

                if(num[i]!=num[to]) deg[num[to]]++;

            }

        }

        ans=0;

        for(int i=1;i<=cnt;i++) if(deg[i]==0)

            ans+=cost[i];

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

    }

    return 0;

}
巴特西

HDU - 5934

tarjan 视频讲解

最新文章

热门文章
