題目鏈接：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
|