用kruskal86分re了1个点QwQ求助(本地对的)
查看原帖
用kruskal86分re了1个点QwQ求助(本地对的)
399402
tabuloforme楼主2022/8/11 10:47
#include<bits/stdc++.h>
using namespace std;
int f[10005],n,m;
long long sum=0;
struct M{
	int x,y,z;
}a[200005];
int cmp(M a,M b){
	return a.z<b.z;
}
int find(int a){
	if(f[a]!=a)f[a]=find(f[a]);
	return f[a];
}
void unionn(int a,int b){
	a=find(a);
	b=find(b);
	f[b]=a; 
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>a[i].x>>a[i].y>>a[i].z;
	for(int i=1;i<=10000;i++)f[i]=i;
	sort(a+1,a+m+1,cmp);
	int s=n;
	for(int i=1;i<=s-1;i++)
		if(find(a[i].x)!=find(a[i].y)){
			unionn(a[i].x,a[i].y);
			sum+=a[i].z;
		}
		else
		s++;
	int p=find(1);
	for(int j=2;j<=n;j++){
		int q=find(j);
		if(p!=q){
			cout<<"orz";
			return 0;
		}
	}
	cout<<sum;
return 0; 
} 
2022/8/11 10:47
加载中...