题解：P1195 口袋的天空

思路

这一题可以用并查集来做。

因为是求最小代价，所以可以先按照代价把每个关系从小到大排序，优先连代价小的云。设

cnt

为棉花糖个数，一开始

cnt

为

n

（天上

n

朵云相当于

n

个棉花糖），接着遍历

i

从第

1

个关系到第

m

个关系，在第

i

个关系中，如果云

x

和

y

之间不连通，那么就可以合并云

x

和

y

，合并后棉花糖就少了一朵，所以

cnt

减

1

，代价加上

l

。当

cnt = k

时，输出代价，遍历完之后如果

cnt

还是大于

k

，则输出 No Answer。

注意：当

k > n

时，输出 No Answer。

代码

CPP

#include <bits/stdc++.h>
using namespace std;
struct node{
	int x, y, l;
}a[10005];
int fa[1005];
bool cmp(node aa, node bb){
	return aa.l < bb.l;
}
int find(int x){
    if(fa[x] == x) return x;
    else return fa[x] = find(fa[x]);
}
bool merge(int x, int y){
	int rx = find(x), ry = find(y);
	if(rx == ry) return false;
	fa[rx] = ry;
	return true;
}
int main(){
	for(int i = 1; i < 1005; i++){
		fa[i] = i;
	}
	int n, m, k;
	cin >> n >> m >> k;
	for(int i = 1; i <= m; i++){
		cin >> a[i].x >> a[i].y >> a[i].l;
	}
	if(k > n){
		cout << "No Answer" << endl;
		return 0;
	}
	sort(a + 1, a + m + 1, cmp);
	int cnt = n;
	int ans = 0;
    if(cnt == k){
		cout << ans << endl;
		return 0;
	}
	for(int i = 1; i <= m; i++){
		if(merge(a[i].x, a[i].y) == true){
			cnt--;
			ans += a[i].l;
		}
        if(cnt == k){
			cout << ans << endl;
			return 0;
		}
	}
	cout << "No Answer" << endl;
}

update 2025/8/24 发布题解

update 2025/9/24 更新代码

题解：P1195 口袋的天空

文章操作

思路

代码

相关推荐

评论

题解：P1195 口袋的天空