题目背景

奶牛爱干草

题目描述

\(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\)，并且每次向MST中加一条边时就更新最大值，最后输出最大值。然后……就做完了。

代码：

#include<algorithm>
#include<cstdio>
#define maxn 10001
using namespace std;
int n,maxx,k,m,fa[2001];
struct node {
  int u,v,w;
}e[maxn];
inline bool cmp(node a, node b) {return a.w<b.w;}
inline int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void uni(int x,int y) {x=find(x),y=find(y);fa[y]=x;}
int main() {
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;++i) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
  sort(e+1,e+1+m,cmp);
  for(int i=1;i<=n;++i) fa[i]=i;
  for(int i=1;i<=m;++i) {
    if(find(e[i].u)!=find(e[i].v)) {
      maxx=max(maxx,e[i].w);
      uni(e[i].u,e[i].v);
      k++;  
    }
    if(k==n-1) break;
  }
  printf("%d\n",maxx);
  return 0;
}