题目链接:http://poj.org/problem?id=2485
又被坑了一把,求的是最小生成树的最大边的长度,无端奉献了两次WA。。
![](/Images/OutliningIndicators/ContractedBlock.gif) 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
|