洛谷题单指南-最小生成树-P1195 口袋的天空

原题链接：https://www.luogu.com.cn/problem/P1195

题意解读：在图中选择若干边，构成k个连通块时，求所选择的边的最小权值和。

解题思路：

在kruskal算法中，从小到大枚举每条边u->v，加入并查集使得u->v之间连通，计算连通块达到k个时，此时所选择的所有边权值之和就是最小的权值和。

证明：反证法。如果存在更小权值和，与最小生成树的定义矛盾。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1005, M = 10005;
struct Edge
{
    int u, v, w;
} edges[M];
int p[N];
int n, m, k, ans;

bool cmp(Edge a, Edge b)
{
    return a.w < b.w;
}

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

bool kruskal()
{
    int cnt = n; //初始连通块数量
    sort(edges + 1, edges + m + 1, cmp);
    for(int i = 1; i <= n; i++) p[i] = i;
    for(int i = 1; i <= m; i++)
    {
        int a = find(edges[i].u);
        int b = find(edges[i].v);
        if(a != b)
        {
            p[a] = b;
            ans += edges[i].w;
            if(--cnt == k) return true; //每次合并连通块都减少一个，如果减少到k则返回
        }
    } 
    return false;
}

int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++)
    {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
    if(kruskal()) cout << ans;
    else cout << "No Answer";
    return 0;
}