86pts Kruskal求调,悬棺QAQ
查看原帖
86pts Kruskal求调,悬棺QAQ
1122029
icebear233楼主2024/7/29 22:10
#include<bits/stdc++.h>
using namespace std;
int n,m,b,ans;
int fa[50005];
struct node{
	int u,v,w;
}e[200005];
bool cmp(node x,node y){
	return x.w<y.w;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1,x,y;i<=m;i++){
		cin>>e[i].u>>e[i].v>>e[i].w;	
	}
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=m;i++){
		if(b==n-1){
			cout<<ans;
			return 0;
		}
		int x=e[i].u,y=e[i].v,w=e[i].w;
		while(fa[x]!=x){
			x=fa[x];
		}
		while(fa[y]!=y){
			y=fa[y];
		}
		if(x==y){
			continue;
		}
		else{
			fa[y]=x;
			ans+=w;
			b++;
		}
	}
	cout<<"orz";
	return 0;
}
2024/7/29 22:10
加载中...