过了,但有一个地方没想明白
查看原帖
过了,但有一个地方没想明白
1268524
DX3906_ourstar楼主2024/8/2 16:16

代码:

#include<iostream>
#include<algorithm>
#define re register
using namespace std;

const int N = 1e6 + 5;

int n,m,k,ans,cnt;
int fa[N];

struct node{
	int x,y,w;
}a[N];

inline int find(int x){
	if(x == fa[x]){
		return x;
	}else{
		return fa[x] = find(fa[x]);
	}
}

inline bool cmp(node a,node b){
	return a.w < b.w;
}

inline void cs(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

int main(){
	cs();
	cin>>n>>m>>k;
	for(re int i = 1;i <= n;i ++){
		fa[i] = i;
	}
	for(re int i = 1;i <= m;i ++){
		int x,y,l;
		cin>>x>>y>>l;
		a[i].x = x;
		a[i].y = y;
		a[i].w = l;
	}
	sort(a + 1,a + m + 1,cmp);
	for(re int i = 1;i <= n;i ++){
		int x = find(a[i].x);
		int y = find(a[i].y);
		if(x != y){
			fa[x] = y;
			ans += a[i].w;
			cnt ++;
			if(cnt >= n - k){
				cout<<ans<<"\n";
				return 0;
			}
		}
	}
	cout<<"No Answer\n";
	return 0;
}

第5454行,cnt >= n - k是什么意思?怎么来的?为什么这个条件为真时,就可输出答案?

这个是自己一通乱试试出来的,没搞懂

2024/8/2 16:16
加载中...