题目描述
Bessie 计划调查 N(2≤N≤2000)个农场的干草情况,它从 1号农场出发。农场之间总共有 M(1≤M≤10000)条双向道路,所有道路的总长度不超过 10^9.有些农场之间存在着多条道路,所有的农场之间都是连通的.
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
算法1
(Kruskal)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,INF=0x3f3f3f3f;
int dis[N],f[N],n,m,cnt;//cnt表示边数
int find(int x)//并查集常规操作之一
{
return f[x]==x?x:f[x]=find(f[x]);//在找爸爸的同时进行优化(把自己这一块的最大爸爸作为f[x]储存的值)
}
struct Edge//结构体存数据
{
int a,b,w;
bool operator<(const Edge &W)const{
return w<W.w;
}//重载运算符方便之后的sort排序,或者用下面的cmp
}edges[N];
/*
bool cmp(Edge a,Edge b)
{
return a.w<b.w;
}
*/
int Kruskal()//主角登场
{
for(int i=1;i<=n;i++) f[i]=i;//并查集常规操作之二,把自己一开始的爸爸设成自己
sort(edges,edges+m);//按权重从小到大排序
/*
sort(edges,edges+m,cmp);
*/
int res=0;
for(int i=0;i<m;i++)
{
int a=edges[i].a,b=edges[i].b,w=edges[i].w;
int f1=find(a),f2=find(b);
if(f1!=f2)//最大爸爸不同,即这两块地方没有连上
{
f[f1]=f2;//或者f[f2]=f1;
res=w;
cnt++;//手动连边
}
}
if(cnt<n-1) return INF;//连不上的情况下返回INF
return res;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
edges[i]={a,b,w};
}
int ans=Kruskal();
printf("%d\n",ans);
return 0;
}