Summer Holiday (HDU - 1827)

题面

To see a World in a Grain of Sand And a Heaven in a Wild Flower, Hold Infinity in the palm of your hand And Eternity in an hour. —— William Blake

听说lcy帮大家预定了新马泰7日游，Wiskey真是高兴的夜不能寐啊，他想着得快点把这消息告诉大家，虽然他手上有所有人的联系方式，但是一个一个联系过去实在太耗时间和电话费了。他知道其他人也有一些别人的联系方式，这样他可以通知其他人，再让其他人帮忙通知一下别人。你能帮Wiskey计算出至少要通知多少人，至少得花多少电话费就能让所有人都被通知到吗？

输入

多组测试数组，以EOF结束。 第一行两个整数N和M（1<=N<=1000, 1<=M<=2000），表示人数和联系对数。 接下一行有N个整数，表示Wiskey联系第i个人的电话费用。 接着有M行，每行有两个整数X，Y，表示X能联系到Y，但是不表示Y也能联系X。

输出

输出最小联系人数和最小花费。 每个CASE输出答案一行。

样例输入

 112 16
 22 2 2 2 2 2 2 2 2 2 2 2
 31 3
 43 2
 52 1
 63 4
 72 4
 83 5
 95 4
104 6
116 4
127 4
137 12
147 8
158 7
168 9
1710 9
1811 10

样例输出

13 6

提示

无

思路

代码

 1using namespace std;
 2typedef long long ll;
 3const int inf = 0x3f3f3f3f;
 4const int N = 2e4+5;
 5const int M = 5e4+5;
 6
 7struct E {
 8    int to, next;
 9} e[M];
10
11int H[N], tot;
12
13int S[N], top;
14int dfn[N], low[N], bel[N], idx, scc;
15
16int n, m, cost[N];
17int u, v;
18
19int sc[N], id[N];
20
21void add(int from, int to) {
22    e[tot] = {to, H[from]};
23    H[from] = tot++;
24}
25
26void dfs(int u) {
27    dfn[u] = low[u] = ++idx;
28    S[++top]=u;
29
30    for(int i=H[u]; ~i; i=e[i].next) {
31        int v = e[i].to;
32        if(!dfn[v]) {
33            dfs(v);
34            low[u] = min(low[u], low[v]);
35        } else if(!bel[v])
36            low[u] = min(low[u], dfn[v]);
37    }
38    if(low[u]==dfn[u]) {
39        scc++;
40        int t;
41        do {
42            t=S[top--];
43            bel[t]=scc;
44        } while(t!=u);
45    }
46}
47
48void tarjan() {
49    memset(dfn, 0, sizeof(dfn));
50    memset(bel, 0, sizeof(bel));
51    idx = scc = top = 0;
52    for(int i=1; i<=n; i++) {
53        if(!dfn[i])
54            dfs(i);
55    }
56}
57
58void solve(int &num, int &sum) {
59    memset(sc, inf, sizeof(sc));
60    memset(id, 0, sizeof(id));
61
62    for(int i=1; i<=n; i++)
63        sc[bel[i]] = min(sc[bel[i]], cost[i]);
64
65    for(int u=1; u<=n; u++) {
66        for(int i=H[u]; ~i; i=e[i].next) {
67            int v = e[i].to;
68            if(bel[u]!=bel[v]) {
69                id[bel[v]]++;
70            }
71        }
72    }
73
74    int a=0, b=0;
75    for(int i=1; i<=scc; i++) {
76        if(!id[i])
77            num++, sum+=sc[i];
78    }
79}
80
81int main(void) {
82    while(scanf("%d%d", &n, &m)==2) {
83        memset(H, -1, sizeof(H));
84        tot = 0;
85        for(int i=1; i<=n; i++)
86            scanf("%d", &cost[i]);
87        for(int i=0; i<m; i++) {
88            scanf("%d%d", &u, &v);
89            add(u, v);
90        }
91        tarjan();
92        int num=0, sum=0;
93        solve(num, sum);
94        printf("%d %d\n", num, sum);
95    }
96    return 0;
97}