AgriNet ——最小生成树

题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=24534#problem/A

题目大意：

　　给定无向图，邻接矩阵。求最小生成树权值。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 #define MAXN 110
 8 #define MAXM 5009
 9 typedef struct edge {
10   int u, v, w;
11   bool operator < (const edge &other) const {
12     return w < other.w;
13   }
14 }edge;
15 edge edges[MAXM];
16 int parent[MAXN];
17 int n, m, i, j;
18 void init() {
19   for (i = 1; i <= n; ++i) parent[i] = -1;
20 }
21 int find(int x) {
22   int s;
23   for (s = x; parent[s] >= 0; s = parent[s]) ;
24   while (s != x) {
25     int tmp = parent[x];
26     parent[x] = s;
27     x = tmp;
28   }
29   return s;
30 }
31 void Union(int R1, int R2) {
32   int r1 = find(R1), r2 = find(R2), tmp = parent[r1] + parent[r2];
33   if (parent[r1] > parent[r2]) {
34     parent[r1] = r2; parent[r2] = tmp;
35   } else {
36     parent[r2] = r1; parent[r1] = tmp;
37   }
38 }
39 void kruscal() {
40   int sum = 0, num = 0, u, v;
41   init();
42   for (i = 0; i < m; ++i) {
43     u = edges[i].u; v = edges[i].v;
44     if (find(u) != find(v)) {
45       sum += edges[i].w; num++;
46       Union(u, v);
47     }
48     if (num >= n-1) break;
49   }
50   printf("%d\n", sum);
51 }
52 int ma[MAXN][MAXN];
53 int main(void) {
54 #ifndef ONLINE_JUDGE
55   freopen("hust_a.in", "r", stdin);
56 #endif
57   while (~scanf("%d", &n) && n) {
58     for (i = 1; i <= n; ++i) {
59       for (j = 1; j <= n; ++j) {
60         scanf("%d", &ma[i][j]);
61       }
62     }
63     m = 0;
64     for (i = 1; i <= n; ++i) {
65       for (j = 1; j < i; ++j) {
66         edges[m].u = i; edges[m].v = j; edges[m].w = ma[i][j];
67         m++;
68       }
69     }
70     sort(edges, edges+m);
71     kruscal();
72   }
73 
74   return 0;
75 }

这题以前做过，模板题