kruskal（克鲁斯卡尔）算法

#include <bits/stdc++.h>
using namespace std;
int n,m,a,b;
struct edge{
	int start,to,val;
}bian[200007];
int f[200007];
int ans=0;
int find(int x){//并查集
	if(f[x]==x) return x;
	else return f[x]=find(f[x]);
}
bool cmp(edge a,edge b){
	return a.val<b.val;
}//排序
int total;
inline void kruskal(){//枚举排好序的每条边
	for(int i=1;i<=m;i++){
		int u=find(bian[i].start);
		int v=find(bian[i].to);
		if(u==v) continue;
		ans=max(ans,bian[i].val);
		f[u]=v;
		total++;
		if(find(a)==find(b)) break;//说明已经建立好了从a到b的最小生成树
	}
}
int main(){
	scanf("%d%d%d%d",&n,&m,&a,&b);
	if(a==b){//特判一下
		cout<<0;
		return 0;
	}
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",&bian[i].start,&bian[i].to,&bian[i].val);
	}
	sort(bian+1,bian+m+1,cmp);
	kruskal();
	printf("%d",ans);
	return 0;
}