题目背景
奶牛爱干草
题目描述
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。
输出格式：
一个整数，表示最小生成树中的最长边的长度。
输入输出样例
输入样例#1：
3 3
1 2 23
2 3 1000
1 3 43
输出样例#1：
43
并查集 kruskal(仅代表个人立场，勿喷。。)
传送门 Out of Hay
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio> using namespace std; int maxn,n,m,i,tot,j,fa[];
struct node{
int u,v,w;
}e[];
bool cmp(node a,node b)
{
return a.w<b.w;
}
inline int qr(){
int x=,f=;char ch=getchar();
while(ch>''||ch<''){
if(ch=='-') f=-;
ch=getchar();
}
while(ch>=''&&ch<=''){
x=x*+(int)ch-;
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=;i<=n;++i) fa[i]=i;
for(i=;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+,cmp);
for(i=;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;
}