90分并查集求助!!
查看原帖
90分并查集求助!!
568637
liang302楼主2021/12/21 18:13
#include <bits/stdc++.h>
using namespace std;

int father[50005];
int isroot[50005];
struct way{
	int x,y,z;
}a[100005];

int findfather(int x) {
	int a=x;
	while(x!=father[x])
		x=father[x];
	while(a!=father[a]) {
		int z=a;
		a=father[a];
		father[z]=x;

	}

}
void Union(int x,int y) {

	int faX=findfather(x);
	int faY=findfather(y);
	if(faX!=faY)
		father[faX]=faY;

}
void init(int n) {
	for(int i=1; i<=n; i++) {
		isroot[i]=false;
		father[i]=i;
	}
}
bool cmp(way a ,way b){
	return a.z<b.z;
}
int main() {
	int n,m,k,time=0;

		cin>>n;
//		if(n==0) break;
		cin>>m>>k;
		init(n);
		int z,x,y;
		
		
		for(int i=1; i<=m; i++) {
			cin>>a[i].x>>a[i].y>>a[i].z;

			
		}
//		cout<<n-1<<endl;
	sort(a ,a+m+1 , cmp);
//	for(int i=1;i<=m;i++) cout<<a[i].z<<" ";
	for(int i=1;i<=m;i++){
		if(findfather(a[i].x)!=findfather(a[i].y)) {
				Union(a[i].x,a[i].y);
				n--;
				time+=a[i].z;
			}
		if(n==k) {
			cout<<time;return 0;

		}

	}
	cout<<"No Answer";




//	cout<<"-1";

	


	return 0;
}




2021/12/21 18:13
加载中...