Out of Hay

来源：USACO 2005 March Silver
OJ题号：洛谷1547、POJ2395
思路：
Kruskal求最小生成树，记录最大边。
 1 #include<cstdio>
 2 #include<cctype>
 3 #include<algorithm>
 4 inline int getint() {
 5     char ch;
 6     while(!isdigit(ch=getchar()));
 7     int x=ch^'0';
 8     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
 9     return x;
10 }
11 class DisjointSet {
12     private:
13         static const int N=2001;
14         int anc[N];
15         int Find(const int x) {
16             return (x==anc[x])?x:(anc[x]=Find(anc[x]));
17         }
18     public:
19         DisjointSet(const int n) {
20             for(int i=1;i<=n;i++) {
21                 anc[i]=i;
22             }
23         }
24         bool isConnected(const int x,const int y) {
25             return Find(x)==Find(y);
26         }
27         void Union(const int x,const int y) {
28             anc[Find(x)]=Find(y);
29         }
30 };
31 struct Edge {
32     int u,v,w;
33     bool operator < (const Edge &x) const {
34         return w<x.w;
35     }
36 };
37 int main() {
38     int n=getint(),m=getint();
39     DisjointSet s(n);
40     Edge e[m];
41     for(int i=0;i<m;i++) {
42         e[i].u=getint(),e[i].v=getint(),e[i].w=getint();
43     }
44     std::sort(&e[0],&e[m]);
45     int ans=0;
46     for(int i=0;i<m;i++) {
47         if(s.isConnected(e[i].u,e[i].v)) continue;
48         s.Union(e[i].u,e[i].v);
49         ans=e[i].w;
50     }
51     printf("%d
",ans);
52     return 0;
53 }