【luogu P1195 口袋的天空】 题解

题目链接：https://www.luogu.org/problemnew/show/P1195

嗯~我是被题目背景吸引到才做的，想吃棉花糖啦！

话说回来，这道题其实很容易就能想明白，k棵最小生成树。

我们用kruskal的思想，每次连接最小代价的边。假设一开始有n棵树，那么我们每次连接两朵云彩就会减少一棵树。

我们设cnt为生成树的数量，每次连接就会是cnt-1-1-1-1....直到cnt == k，就好啦~

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100000;

int n,m,k,fa[maxn],cnt,ans = 0;

int find(int x)
{
    return fa[x] == x?x:fa[x] = find(fa[x]);
}

struct edge{
    int u,v,w;
}e[maxn];

int cmp(edge a,edge b)
{
    return a.w<b.w;
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    
    for(int i = 1; i <= n; i++) 
    {
        fa[i] = i;
    }
    
    for(int i = 1; i <= m; i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        e[i].u = x;
        e[i].v = y;
        e[i].w = z;
    }
    cnt = n;
    sort(e+1,e+1+m,cmp);
    
    for(int i = 1; i <= m; i++)
    {
        if(cnt <= k) break;
        
        int x = find(e[i].u);
        int y = find(e[i].v);
        if(x!=y)
        {
            fa[x] = y;
            ans += e[i].w;
            cnt--;
        }
        
    }
    
    if(cnt == k) 
    {
        printf("%d",ans);
        return 0;
    }
    else
    {
        printf("No Answer");
        return 0;
    }
}