题解：P1195 口袋的天空

chenlc · 2025-08-24 14:08:12 · 题解

思路

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

因为是求最小代价，所以可以先按照代价把每个关系从小到大排序，优先连代价小的云。设 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。

代码

#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 更新代码