求调 30分 最小生成树
  • 板块P1396 营救
  • 楼主幽灵特工
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/5/10 17:10
  • 上次更新2023/11/4 23:26:05
查看原帖
求调 30分 最小生成树
332549
幽灵特工楼主2021/5/10 17:10
#include <bits/stdc++.h>
using namespace std;
int n,m,s,t;
int fa[30001];
struct edges
{
	int from,to,w;
	edges(int a,int b,int c){
		from=a;to=b;w=c;
	}
};
std::vector<edges> edge;
bool cmp(edges a,edges b){
	return a.w<b.w;
}
int find (int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}

int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m>>s>>t;
	int u,v,w;
	for(int i=0;i<m;i++){
		cin>>u>>v>>w;
		edge.push_back(edges(u,v,w));
		edge.push_back(edges(v,u,w));
	}
	for(int i=0;i<n;i++)fa[i]=i;
	sort(edge.begin(),edge.end(),cmp);
	for(int i=0;i<n;i++){
		int x=edge[i].from,y=edge[i].to;
		if(find(x)==find(y))continue;
		fa[x]=y;
		if(find(s)==find(t)){
			cout<<edge[i].w;
			return 0;
		}
	}
}
2021/5/10 17:10
加载中...