最小生成树求救
查看原帖
最小生成树求救
232507
OK咯莫名其妙楼主2021/7/16 15:12
#include<bits/stdc++.h>
using namespace std;
struct node{
	int u,v,w;
}e[10005];
int fa[30005];
int n,m,s,t;
int find(int a){
	if(fa[a]!=a)
		fa[a]=find(fa[a]);
	return fa[a];
}
int uni(int a,int b){
	fa[find(b)]=find(a);
}
int cmp(node a,node b){
	return a.w<b.w;
}
int main(){
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++)
	{
		cin>>e[i].u>>e[i].v>>e[i].w;
	}
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++){
		int x=find(e[i].u),y=find(e[i].v);
		if(x!=y){
			fa[x]=y;
		}
		if(find(s)==find(t)){
			cout<<e[i].w<<endl;
			return 0;
		}
	}
	
}
2021/7/16 15:12
加载中...