P1195 题解

ikunTLE · 2025-08-23 21:49:19 · 题解

题目传送门

思路

可以将题目理解为：一共有 N 个点，要选择一些边，连接边两端的点，使得有 K 个连通块，求操作所需的最小边权。

贪心地，我们尽量每个点与连通块只有一条边相连，使得代价最小。不难发现，这其实是在求最小生成树。

这里介绍一下 Kruskal 求最小生成树。

算法介绍

Kruskal 本质上是一种贪心算法。

先想一下第一步该怎么连。不难想到，一定优先将边权最小的边两边的点连接。这样一定是减少一个连通块所需的最小代价。

那么第二步该怎么连呢？首先可以想到要连边权次小的边。然后再连第 3 小的，第 4 小的。但是这样对吗？如果边两端的点已经联通，那么这条边就可以不用连接了。也就是说，我们每一步要贪心地连接两个不连通的点中最小的边的两端的连通块相连。容易想到可以用并查集合并连通块。

上面有点绕，再来梳理一下思路：

• 首先将每条边存下来并按照边权从小到大排序。
• 选择当前边权最小的边，如果 fa_u\ne fa_v，说明该边的两点不在同一连通块内，需要合并两点，并将答案加入该边的权值；否则不做操作。
• 重复执行直至合并了 n-k 次，这样刚好构成 k 棵树。
• 如果无论如何都执行不满 n-k 次，说明该图无法构成 k 棵树，无解。

注意事项

• 当 n=k 时，无需合并就是 k 个连通块。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e4+10;
int n,m,k,fa[N];
void _init(){
    for(int i=1;i<=n;++i)
        fa[i]=i;
    return;
}
int _find(int x){
    if(x==fa[x])
        return x;
    fa[x]=_find(fa[x]);
    return fa[x];
}
void _merge(int x,int y){
    int xx=_find(x),yy=_find(y);
    if(xx!=yy)
        fa[xx]=yy;
    return;
}
struct node{
    int u,v,w;
    friend bool operator<(const node cmp_x,const node cmp_y){
        return cmp_x.w<cmp_y.w;
    }
}a[N];
void kruskal(){
    sort(a+1,a+m+1);
    _init();
    int cnt=0,sum=0;
    for(int i=1;i<=m;++i){
        if(_find(a[i].u)!=_find(a[i].v)){
            _merge(a[i].u,a[i].v);
            ++cnt,sum+=a[i].w;
        }
        if(cnt==n-k){
            printf("%d\n",sum);
            return;
        }
    }
    printf("No Answer\n");
    return;
}
int main(){
    n=read(),m=read(),k=read();
    if(n==k)
        return printf("0\n"),0;
    for(int i=1;i<=m;++i)
        a[i]={read(),read(),read()};
    kruskal();
    return 0;
}