Kruskal10分,求助
查看原帖
Kruskal10分,求助
351363
baogeger楼主2021/4/25 17:27

感觉没有问题?

#include<bits/stdc++.h>
using namespace std;

struct wen{
	int x;
	int y;
	int quan;
	bool flag=0;
};


bool cmp(wen x,wen y){
	return x.quan<y.quan;
}
bool G[20010][20010];

int per[20010];//加入并查集
 
void chushihua(int n){
	for(int i=1;i<=n;i++){
		per[i]=i;
	}
}//初始化 

int find_per(int n){
	if(per[n]=n) return n;//如果一个点的上级是他自己,就返回; 
	return find_per(per[n]);//否则递归找上级的上级,直到顶端; 
}//查找 

void hebing(int i,int j){
	int n=find_per(i);//随便找
	int m=find_per(j);
	per[m]=n;//加入 
}

bool panduan(int n,int m){
	if(find_per(n)==find_per(m)) return false;
	return true;
}//判断
 
int main(){

	int n,m;
	cin>>n>>m;
	chushihua(20010);
	wen bian[m];	
	for(int j=1;j<=m;j++){
		int x1,y1,quan1;
		cin>>x1>>y1>>quan1;
		bian[j].x=x1;
		bian[j].y=y1;
		bian[j].quan=quan1;
		
	}
	//输入 
	sort(bian+1,bian+1+m,cmp);
	//right
	G[1][1]=1;
	int sum=0;//统边 
	int ans =0;
	
	
	while(sum<n-1){
		for(int i=1;i<=m,sum<n-1;i++){
			if(bian[i].flag==false){
				if(G[bian[i].x][bian[i].y]==false&&panduan(bian[i].x,bian[i].y)){
				
					ans+=bian[i].quan;
					sum=sum+1;

					G[bian[i].x][bian[i].y]=true;
					bian[i].flag=true;
					hebing(bian[i].x,bian[i].y) ;

					continue; 
			}
			}
		}
		
	}
	cout<<ans; 
	return 0;
	
} 
2021/4/25 17:27
加载中...