奶牛爱干草
Bessie 计划调查N (2 <= N <= 2,000)个农场的干草情况，它从1号农场出发。农场之间总共有M (1 <= M <= 10,000)条双向道路，所有道路的总长度不超过1,000,000,000。有些农场之间存在着多条道路，所有的农场之间都是连通的。
Bessie希望计算出该图中最小生成树中的最长边的长度。
输入格式：
两个整数N和M。
接下来M行，每行三个用空格隔开的整数A_i， B_i和L_i，表示A_i和 B_i之间有一条道路长度为L_i。
输出格式：
一个整数，表示最小生成树中的最长边的长度。
3 3 1 2 23 2 3 1000 1 3 43
43
并查集 kruskal(仅代表个人立场，勿喷。。)
#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> using namespace std; int maxn,n,m,i,tot,j,fa[2001]; struct node{ int u,v,w; }e[20001]; bool cmp(node a,node b) { return a.w<b.w; } inline int qr(){ int x=0,f=1;char ch=getchar(); while(ch>‘9‘||ch<‘0‘){ if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘){ x=x*10+(int)ch-48; ch=getchar(); } return x*f; } int find(int k) { if(fa[k]==k) return k; else return find(fa[k]); } int main() { int a,b,c; n=qr();m=qr(); for(i=1;i<=n;++i) fa[i]=i; for(i=0;i<m;++i) { a=qr();b=qr();c=qr(); tot++; e[tot].u=a; e[tot].v=b; e[tot].w=c; } sort(e,e+tot+1,cmp); for(i=1;i<=tot;++i) { int fax,fay; fax=find(e[i].u); fay=find(e[i].v); if(fax!=fay){ maxn=maxn>e[i].w?maxn:e[i].w; fa[fay]=fax; } } cout<<maxn; }
原文：http://www.cnblogs.com/ruojisun/p/6259849.html