题目链接：http://poj.org/problem?id=1251 用题意啊，输入什么的来卡人的题最没有节操了 这道题的输入非常之纠结，看了好久没看明白，后来借助着某个大神的博客的翻译（我真不认识啊），弄明白是怎么回事儿了。 输入每行的第一个字符是按照字典序给的，表示起点，然后的数字表示的是从这一点出发有多少条链接不是上面的点的道路，然后是各个道路的终点以及道路的长度，最后求的是最小生成树的边权值，我还是只会kruskal啊……
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 struct edge
9 {
10 int u, v, w;
11 }e[900];
12 int p[30], tot;
13 void add(int x, int y, int z)
14 {
15 tot++;
16 e[tot].u = x;
17 e[tot].v = y;
18 e[tot].w = z;
19 tot++;
20 e[tot].u = y;
21 e[tot].v = x;
22 e[tot].w = z;
23 }
24 int find(int x)
25 {
26 return p[x] != x ? p[x] = find(p[x]) : x;
27 }
28 int cmp(edge a, edge b)
29 {
30 return a.w < b.w;
31 }
32 int main()
33 {
34 int n, r1, r2, ans, k, d;
35 char c, s;
36 while (scanf("%d", &n) != EOF)
37 {
38 tot = ans = 0;
39 memset(e, 0, sizeof(e));
40 if (n == 0) break;
41 for (int i = 0; i < n; i++) p[i] = i;
42 for (int i = 1; i < n; i++)
43 {
44 scanf("\n%c %d", &c, &k);
45 for (int j = 0; j < k; j++)
46 {
47 scanf(" %c %d", &s, &d);
48 add(c - 'A', s - 'A', d);
49 }
50 }
51 sort(e + 1, e + 1 + tot, cmp);
52 for (int i = 1; i <= tot; i++)
53 {
54 r1 = find(e[i].u); r2 = find(e[i].v);
55 if (r1 != r2)
56 {
57 p[r2] = r1;
58 ans += e[i].w;
59 }
60 }
61 printf("%d\n", ans);
62 }
63 return 0;
64
|