題目鏈接：http://poj.org/problem?id=2485
又被坑了一把，求的是最小生成樹的最大邊的長度，無端奉獻了兩次WA。。
  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 #define N 501
9 #define M 250000
10 #define max(a, b) a > b ? a : b
11 int t, a[N][N], p[N], tot;
12 struct edge
13 {
14 int u, v, w;
15 }e[M];
16 int find(int x)
17 {
18 return p[x] != x ? p[x] = find(p[x]) : x;
19 }
20 int cmp(edge a, edge b)
21 {
22 return a.w < b.w;
23 }
24 void add(int x, int y, int z)
25 {
26 tot++;
27 e[tot].u = x; e[tot].v = y; e[tot].w = z;
28 }
29 int main()
30 {
31 int ans, r1, r2, n;
32 cin >> t;
33 while (t--)
34 {
35 cin >> n;
36 ans = tot = 0; memset(e, 0, sizeof(e));
37 for (int i = 0; i < n; i++) p[i] = i;
38 for (int i = 0; i < n; i++)
39 for (int j = 0; j < n; j++)
40 {
41 cin >> a[i][j];
42 if (i != j && a[i][j] > 0) add(i, j, a[i][j]);
43 }
44 sort(e + 1, e + 1 + tot, cmp);
45 for (int i = 1; i <= tot; i++)
46 {
47 r1 = find(e[i].u); r2 = find(e[i].v);
48 if (r1 != r2)
49 {
50 p[r2] = r1;
51 ans = max(ans, e[i].w);
52 }
53 }
54 cout << ans << endl;
55 }
56 return 0;
57
|