克鲁斯卡尔 21分 玄关求调
查看原帖
克鲁斯卡尔 21分 玄关求调
1037011
CandyCai楼主2025/7/24 11:15
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct tu{
	int x,y,z;
}a[200010];
int s[5010];
bool px(tu u,tu v){
	return u.z<v.z;
}
int gf(int ij){
	if(s[ij]==ij){
		return ij;
	}
	return s[ij]=gf(s[ij]);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		s[i]=i;
	}
	for(int i=1;i<=m;i++){
		cin>>a[i].x>>a[i].y>>a[i].z;
	}
	sort(a+1,a+1+m,px);
	int ans=0;
	int add=0;
	for(int i=1;i<=m;i++){
		if(add==n-1){
			break;
		}
		if(gf(a[i].x)!=gf(a[i].y)){
			add++;
			ans+=a[i].z;
			s[a[i].y]=s[a[i].z];
		}
	}
	if(add==n-1){
		cout<<ans;
	}else{
		cout<<"orz";
	}
	return 0;
}

哪位大佬能帮忙调一下啊QwQ

2025/7/24 11:15
加载中...