題目鏈接：http://poj.org/problem?id=1251
用題意啊，輸入什么的來(lái)卡人的題最沒(méi)有節(jié)操了
這道題的輸入非常之糾結(jié)，看了好久沒(méi)看明白，后來(lái)借助著某個(gè)大神的博客的翻譯（我真不認(rèn)識(shí)啊），弄明白是怎么回事兒了。
輸入每行的第一個(gè)字符是按照字典序給的，表示起點(diǎn)，然后的數(shù)字表示的是從這一點(diǎn)出發(fā)有多少條鏈接不是上面的點(diǎn)的道路，然后是各個(gè)道路的終點(diǎn)以及道路的長(zhǎng)度，最后求的是最小生成樹(shù)的邊權(quán)值，我還是只會(huì)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