并查集MLE
  • 板块P1396 营救
  • 楼主Xieaotong
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/3/11 21:21
  • 上次更新2024/3/12 10:00:32
查看原帖
并查集MLE
1056696
Xieaotong楼主2024/3/11 21:21
#include<iostream>
#include<algorithm> 
using namespace std;
const int N=1e4+10;
const int M=2e4+10;
int n,m,s,t;
struct node{
	int u,v;
	int w;
}edge[M];
bool comp(node x,node y){
	return x.w<y.w;
}
int fa[N],ranks[N];
int a[N];
void init(int n){
	for(int i=1;i<=n;i++){
		fa[i]=i;
		ranks[i]=1;
	}
}
int find(int x){
	if(fa[x]==x){
		return x;
	}else{
		fa[x]=find(x);
		return fa[x];
	}
}
void merge(int x,int y){
	int a=find(x);
	int b=find(y);
	if(ranks[a]<ranks[b]){
		fa[a]=b; 
	}else if(ranks[a]>ranks[b]){
		fa[b]=a;
	}else{
		if(a!=b){
			fa[a]=b;
			ranks[b]++;
		}
	}
	return ;
} 
int main(){
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		cin>>edge[i].u>>edge[i].v>>edge[i].w;
	}
	sort(edge+1,edge+1+m,comp);
	init(n);
	for(int i=1;i<=m;i++){
		int x=edge[i].u;
		int y=edge[i].v;
		merge(x,y);
		if(fa[find(s)]==fa[find(t)]){
			cout<<edge[i].w;
			break;
		}
	}
	return 0;
}
2024/3/11 21:21
加载中...