题目背景
奶牛爱干草
题目描述
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算法更好，不需要求最小生成树之和，只需要最后一条边。kruskal特别需要注意的细节是排序时是用总边数排序，经常容易出现细节错误。
#include <bits/stdc++.h>
using namespace std;
const int maxm = 1e4+1;
const int maxn = 2e3+1;
struct edge{
int from, to, cost;
}es[maxm];
int n, m, fa[maxn], rk[maxn];
void rd(){
scanf("%d %d", &n, &m);
for(int i=1; i<=m; i++)
scanf("%d %d %d", &es[i].from, &es[i].to, &es[i].cost);
}
bool cmp(const edge &x, const edge &y){
return x.cost<y.cost;
}
int find(int x){
return fa[x]==x ? x : fa[x]=find(fa[x]);
}
void kruskal(){
sort(es+1, es+m+1, cmp); // 边的总数，不要写成es+n+1
for(int i=1; i<=n; i++){
fa[i] = i;
rk[i] = 0;
}
int cnt = 0; // 第cnt条边
for(int i=1; i<=m; i++){
edge e = es[i];
int fx = find(e.from);
int fy = find(e.to);
if(fx!=fy){
if(rk[fx]<rk[fy])
fa[fx] = fy;
else{
fa[fy] = fx;
if(rk[fx]==rk[fy])
rk[fx]++;
}
cnt++;
if(cnt==n-1){ // 最后一条边
printf("%d", e.cost);
return;
}
}
}
}
int main(){
rd();
kruskal();
return 0;
}