「HDU-1827」Summer Holiday (强联通分量)

发表于 | 分类于 ，

「HDU-1827」Summer Holiday
Tarjan强联通分量+缩点，求最小联系费用

解法

强联通分量+缩点，判断每个强连通分量的入度是否为0，如果为0，则说明没有人能联系到这个分量中的任意一点。在同一强联通分量内，任意两点互相通达，所以只要其入度不为0，就代表整个强联通分量内的点都能被图中其它点通知信息。故Wiskey只要通知所有入度为0的强联通分量中的任意一点，就能通知到所有人。对于每一个入度为0的强联通分量，所需的联系费用即为其中花费最小的节点的费用（即点权最小的点的权值）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int maxn=1000+10;

vector <int> edge[maxn];

int dfn[maxn],low[maxn],cost[maxn],belong[maxn],degree[maxn];
int stack[maxn],index,tot,scc;
bool vis[maxn];

void Tarjan(int v)
{
    dfn[v]=low[v]=++tot;
    stack[++index]=v;
    vis[v]=true;
    for(int i=0;i<edge[v].size();i++)
    {
        int u=edge[v][i];
        if(!dfn[u])
        {
            Tarjan(u);
            low[v]=min(low[v],low[u]);
        }
        else if(vis[u])
            low[v]=min(low[v],dfn[u]);
    }
    if(low[v]==dfn[v])
    {
        int u;
        belong[v]=++scc;
        do
        {
            u=stack[index];
            vis[u]=false;
            belong[u]=scc;
            index--;
        }while(u!=v);
    }
}

int main()
{
    int n,m,u,v;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&cost[i]);
            edge[i].clear();
        }
        while(m--)
        {
            scanf("%d%d",&u,&v);
            edge[u].push_back(v);
        }
        memset(dfn,0,sizeof(dfn));
        memset(degree,0,sizeof(degree));
        tot=index=scc=0;
        for(int i=1;i<=n;i++)
            if(!dfn[i]) Tarjan(i);	//Tarjan求强联通分量+缩点
        int ans=0,sum=0;
        for(int v=1;v<=n;v++)
        {
            for(int j=0;j<edge[v].size();j++)
            {
                int u=edge[v][j];
                if(belong[v]!=belong[u])	//不在同一个强连通分量内
                    degree[belong[u]]++;	//入度+1
            }
        }
        for(int i=1;i<=scc;i++)
        {
            if(!degree[i])	//该强联通分量的入度为0
            {
                ans++;
                int mincost=0x3f3f3f3f;
                for(int j=1;j<=n;j++)
                {
                    if(belong[j]==i)	//该点在强连通分量内
                        mincost=min(mincost,cost[j]);	//求该强联通分量内点权最小的点的权值
                }
                sum+=mincost;
            }
        }
        printf("%d %d\n",ans,sum);
    }
    return 0;
}