P1195 口袋的天空-Kruskal（优先队列+并查集）

口袋的天空

题目背景

小杉坐在教室里，透过口袋一样的窗户看口袋一样的天空。

有很多云飘在那里，看起来很漂亮，小杉想摘下那样美的几朵云，做成棉花糖。

题目描述

给你云朵的个数 $N$，再给你 $M$ 个关系，表示哪些云朵可以连在一起。

现在小杉要把所有云朵连成 $K$ 个棉花糖，一个棉花糖最少要用掉一朵云，小杉想知道他怎么连，花费的代价最小。

输入格式

第一行有三个数 $N,M,K$。

接下来 $M$ 行每行三个数 $X,Y,L$，表示 $X$ 云和 $Y$ 云可以通过 $L$ 的代价连在一起。

输出格式

对每组数据输出一行，仅有一个整数，表示最小的代价。

如果怎么连都连不出 $K$ 个棉花糖，请输出 No Answer。

样例 #1

样例输入 #1

3 1 2
1 2 1
1
2

样例输出 #1

1
1

#include
using namespace std;
typedef long long ll;
#define de(x) cout<<x<<" ";
#define sf(x) scanf("%d",&x);
#define Pu puts("");
const int N=1e3+10,M=2e5+10;
int f[N];
//int u[N],tot;//原本想先建成最小生成树，然后减去最大的（n-k）条边
//但是后来发现如果数据给的边数不够，无法建成树，则一定求解不出来
//正确思路：每次往最小生成树里加一条边，意味着连通块少1。所以一直加直到为k个连通块
//（即选了最小生成树的前n-k条边）
int cnt;
struct E{
    int x,y,u;
};
struct cmp{
    bool operator()(E a,E b){
        return a.u>b.u;
    }
};
priority_queue<E,vector<E>,cmp>q;
int n,m,k;
int ans;
int find(int x){
    if(x==f[x]) return x;
    return f[x]=find(f[x]);
}
void kruskal(){
    for(int i=1;i<=n;i++) f[i]=i;
    int x,y,z;
    int a,b;
    while(!q.empty()){
        x=q.top().x;y=q.top().y;z=q.top().u;q.pop();
        a=find(x);b=find(y);
        if(a!=b){
            if(a>b) f[a]=b;
            else f[b]=a;
            //u[++tot]=z;//储存n-1条边权重的数组
            ans+=z;//总和，即最小生成树

            cnt--;
            if(cnt==0) return ;
        }
    }
} 
int main(){
    cin>>n>>m>>k;
    int x,y,z;
    for(int i=1;i<=m;i++){
        sf(x)sf(y)sf(z)
        q.push(E{x,y,z});
    }
    cnt=n-k;
    kruskal();
    if(cnt) {
        printf("No Answer\n");
        return 0;
    }
    // sort(u+1,u+tot+1);
    // int id=tot;
    // while(k--){
    //     ans-=u[tot--];
    // }
    printf("%d\n",ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67