MST:Out of Hay(POJ 2395)

　　　　　　　　　　　　　　　缺乏粮草

　　题目大意：一群牛要修建一些通道，到各个农场距离总和要最小，求这些通道的最大值

　　水题了，一个Kruskal搞定

 1 #include <iostream>
 2 #include <functional>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 typedef int Postion;
 7 typedef struct _edge
 8 {
 9     Postion from;
10     Postion to;
11     int cost;
12 }Edge_Set;
13 int fcomp(const void *a, const void *b)
14 {
15     return (*(Edge_Set *)a).cost - (*(Edge_Set *)b).cost;
16 }
17 
18 static Edge_Set edge[10001 * 2];
19 static Postion Set[2002];
20 
21 void Kruskal(const int, const int);
22 Postion Find(Postion);
23 void Union(Postion, Postion);
24 
25 int main(void)
26 {
27     int Node_Sum, Path_Sum;
28     while (~scanf("%d%d", &Node_Sum, &Path_Sum))
29     {
30         for (int i = 0; i < Path_Sum; i++)
31             scanf("%d%d%d", &edge[i].from, &edge[i].to, &edge[i].cost);
32         qsort(edge, Path_Sum, sizeof(Edge_Set), fcomp);
33         Kruskal(Node_Sum, Path_Sum);
34     }
35 
36     return 0;
37 }
38 
39 Postion Find(Postion x)
40 {
41     if (Set[x] < 0)
42         return x;
43     return Set[x] = Find(Set[x]);
44 }
45 
46 void Union(Postion px, Postion py)
47 {
48     if (Set[px] < Set[py])
49     {
50         Set[px] += Set[py];
51         Set[py] = px;
52     }
53     else
54     {
55         Set[py] += Set[px];
56         Set[px] = py;
57     }
58 }
59 
60 void Kruskal(const int Node_Sum, const int Path_Sum)
61 {
62     int edge_sum = 0, max_edge = -1;
63     long long ans = 0;
64     Postion px, py, from, to;
65     memset(Set, -1, sizeof(Set));
66 
67     for (int i = 0; edge_sum < Node_Sum && i < Path_Sum; i++)
68     {
69         from = edge[i].from; to = edge[i].to;
70         px = Find(from); py = Find(to);
71         
72         if (px != py)
73         {
74             ans += edge[i].cost;
75             Union(px, py);
76             edge_sum++;
77             max_edge = max(max_edge, edge[i].cost);
78         }
79     }
80     printf("%d
", max_edge);
81 }