http://acm.hdu.edu.cn/showproblem.php?pid=1233
1 #include<cstdio>
2 #include<algorithm>
3 #include<cstring>
4 using namespace std;
5 #define N 10000
6 int u[N], v[N], w[N], r[N], p[N];
7 int cmp(int i, int j) {return w[i] < w[j];}
8 int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
9 int n,m;
10 int kruskal()
11 {
12 int ans=0;
13 for(int i = 0; i <=n; ++i) p[i] = i;
14 for(int i = 0; i < m; ++i) r[i] = i;
15 sort(r,r+m,cmp);
16 for(int i = 0, cnt = 0; i < m && cnt < n - 1; ++i)
17 {
18 int e = r[i]; int x = find(u[e]); int y = find(v[e]);
19 if(x != y){ ans += w[e]; cnt++; p[x] = y; }
20 }
21 return ans;
22 }
23 int main()
24 {
25 while(scanf("%d", &n),n)
26 {
27 m=0;
28 char c[2];
29 for(int i = 0; i < n - 1; ++i)
30 {
31 int cnt;
32 scanf("%s%d", c, &cnt);
33 for(int j = 0; j < cnt; ++j)
34 {
35 int we;char cc[2];
36 scanf("%s%d", cc, &we);
37 u[m] = c[0] - 'A';
38 v[m] = cc[0] - 'A';
39 w[m] = we;
40 m++;
41 }
42 }
43 int ans = kruskal();
44 printf("%d\n", ans);
45 }
46 return 0;
47 }
48
posted on 2011-09-12 21:40
ACSeed 閱讀(274)
評論(0) 編輯 收藏 引用