P1195 口袋的天空

· · 题解

P1195 口袋的天空

题目翻译：

我们要把n朵云连成k个连通块，使花费最小

思路：

我们若要使花费最小，也就是使其连的边越少，那就相当于要连k个树，因为树的边最少，因此运用贪心的思想，我们只需要连接1棵最小生成树,在留下k-1个点不连即可

实现：

最小生成树就用kruskal来维护，而我们只需要在建树时，检查一下当前连的点数是否等于k-n即可，若到了，则输出，结束

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N=20010;
struct edge{
    int u,v,w;
    bool operator<(const edge &a){return w<a.w;}
}e[N];
int fa[N];
int find(int x){
    if(fa[x]==x)return x;
    else{
        return fa[x]=find(fa[x]);
    }
}
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(int i=1;i<=m;i++){
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    sort(e+1,e+1+m);
    int cnt(0),ans(0);
    for(int i=1;i<=m;i++){
        if(find(e[i].u)!=find(e[i].v)){
            fa[find(e[i].u)]=find(e[i].v);
            cnt++;
            ans+=e[i].w;
            if(cnt==n-k){
                cout<<ans;
                return 0;
            }
        }
    }
    cout<<"No Answer";

}
}

最小生成树讲解