裸的最小生成樹，我用kruskal，并查集搞定，但是不知道為什么，題目的樣例給錯了，冒險交了一下，竟然A了…… 題目鏈接 http://poj.org/problem?id=1861  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <algorithm>
6 #include <cmath>
7 using namespace std;
8 #define M 30010
9 #define N 1010
10 #define max(a, b) a > b ? a : b;
11 struct edage
12 {
13 int u, v, w;
14 bool j;
15 }e[M];
16 int p[N], tot;
17 int find(int x)
18 {
19 return p[x] != x ? p[x] = find(p[x]) : x;
20 }
21 void init(int x, int y, int z)
22 {
23 tot++;
24 e[tot].u = x;
25 e[tot].v = y;
26 e[tot].w = z;
27 e[tot].j = 0;
28 tot++;
29 e[tot].u = y;
30 e[tot].v = x;
31 e[tot].w = z;
32 e[tot].j = 0;
33 }
34 int cmp(edage a, edage b)
35 {
36 return a.w < b.w;
37 }
38 int main()
39 {
40 int n, m;
41 int x, y, z;
42 int r1, r2;
43 int cnt;
44 int maxi;
45 while (scanf("%d%d", &n, &m) != EOF)
46 {
47 cnt = 0; maxi = 0;
48 for (int i = 1; i <= n; i++)
49 p[i] = i;
50 tot = 0; memset(e, 0, sizeof(e));
51 while (m--)
52 {
53 scanf("%d%d%d", &x, &y, &z);
54 init(x, y, z);
55 }
56 sort(e + 1, e + tot + 1, cmp);
57 for (int i = 1; i <= tot; i++)
58 {
59 r1 = find(e[i].u); r2 = find(e[i].v);
60 if (r1 != r2)
61 {
62 p[r2] = r1;
63 cnt++;
64 e[i].j = 1;
65 maxi = max(e[i].w, maxi);
66 }
67 }
68 printf("%d\n%d\n", maxi, cnt);
69 for (int i = 1; i <= tot; i++)
70 {
71 if (e[i].j) printf("%d %d\n", e[i].u, e[i].v);
72 }
73 }
74 return 0;
75
|