poj2395 Out of Hay

思路：
MST
实现：
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <vector>
 4 #include <algorithm>
 5 #include <cmath>
 6 using namespace std;
 7 
 8 struct edge
 9 {
10     int a, b, cost;
11 };
12 edge es[10005];
13 int ran[2005];
14 int par[2005];
15 int n, m, x, y, c;
16 
17 void init(int n)
18 {
19     for (int i = 0; i < n; i++)
20     {
21         par[i] = i;
22         ran[i] = 0;
23     }
24 }
25 
26 int find(int x)
27 {
28     if (par[x] == x)
29         return x;
30     return par[x] = find(par[x]);
31 }
32 
33 void unite(int x, int y)
34 {
35     x = find(x);
36     y = find(y);
37     if (x == y)
38         return;
39     if (ran[x] < ran[y])
40     {
41         par[x] = y;
42     }
43     else
44     {
45         par[y] = x;
46         if (ran[x] == ran[y])
47         {
48             ran[x] ++;
49         }
50     }
51 }
52 
53 bool same(int x, int y)
54 {
55     return find(x) == find(y);
56 }
57 
58 bool cmp(const edge & a, const edge & b)
59 {
60     return a.cost < b.cost;
61 }
62 
63 int kru()
64 {
65     init(n);
66     sort(es, es + m, cmp);
67     int maxn = 0;
68     for (int i = 0; i < m; i++)
69     {
70         if (!same(es[i].a, es[i].b))
71         {
72             unite(es[i].a, es[i].b);
73             maxn = max(maxn, es[i].cost);
74         }
75     }
76     return maxn;
77 }
78 
79 int main()
80 {
81     scanf("%d %d", &n, &m);
82     for (int i = 0; i < m; i++)
83     {
84         scanf("%d %d %d", &x, &y, &c);
85         es[i].a = x;
86         es[i].b = y;
87         es[i].cost = c;
88     }
89     int tmp = kru();
90     printf("%d
", tmp);
91     return 0;
92 }