hdu 3072 Intelligence System

本文从WordPress迁移而来, 查看全部WordPress迁移文章

强连通分量 + 简单最小树形图

题意：读不懂这个题意，找别人说就是，对有向图求一次强连通分量缩点得到一个DAG，而且题意保证缩点后只会有一个入度为0的点，接下来就是求最小树形图，这题比较简单，因为已经是DAG不会有环，只需要执行最小树形图的其中一个步骤就是给每个点找一条最小的入度就可以了

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
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
#define N 50010
#define M 100010
#define INF 0x3f3f3f3f
#define cl memset
#define pii pair<int,int>
#define pb push_back
#define mp make_pair

int n,tot,head[N];
struct edge{
    int v,w,next;
}e[M];
int dfn[N],low[N],dcnt,bcnt,belong[N],stack[N],top,ins[N];
vector<pii>ver[N];
int inde[N],root;
queue<int>q;
int dp[N],val[N],inq[N];

inline void add(int u,int v,int w){
    e[tot].v = v; e[tot].w = w; 
    e[tot].next = head[u]; head[u] = tot++;
}

void rebuild(){
    for(int i = 0; i <= bcnt; i++){
        ver[i].clear();
        inde[i] = 0;
    }
    for(int i = 0; i < n; i++)
        for(int j = head[i]; j != -1; j = e[j].next){
            int v = e[j].v , w = e[j].w;
            if(belong[i] == belong[v]) continue;
            ver[belong[i]].pb(mp(belong[v],w));
            inde[belong[v]]++;
        }
    for(int i = 1; i <= bcnt; i++)
        if(inde[i] == 0){
            root = i; break;
        }
}

void tarjan(int u){
    dfn[u] = low[u] = ++dcnt;
    stack[++top] = u; ins[u] = 1;
    for(int k = head[u]; k != -1; k = e[k].next){
        int v = e[k].v;
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if(ins[v])
            low[u] = min(low[u],dfn[v]);
    }
    if(dfn[u] == low[u]){
        ++bcnt;
        while(true){
            int x = stack[top--];
            ins[x] = 0;
            belong[x] = bcnt;
            if(x == u) break;
        }
    }
}
void scc(){
    dcnt = bcnt = top = 0;
    cl(ins,0,sizeof(ins));
    cl(dfn,0,sizeof(dfn));
    for(int i = 0; i < n; i++)
        if(!dfn[i])
            tarjan(i);
}

void solve(){
    cl(val,0x3f,sizeof(val));
    for(int i = 1; i <= bcnt; i++)
        for(int j = 0; j < ver[i].size(); j++)
            val[ver[i][j].first] = min(val[ver[i][j].first],ver[i][j].second);
    int res = 0;
    for(int i = 1; i <= bcnt; i++)
        if(inde[i])
            res += val[i];
    printf("%d\n",res);
}
int main(){
    int m;
    while(scanf("%d%d",&n,&m)!=EOF){
        tot = 0;
        cl(head,-1,sizeof(head));
        while(m--){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
        }
        scc();
        rebuild();
        solve();
    }
    return 0;
}