题解：P1195 口袋的天空

yyycj · 2025-08-23 21:52:15 · 题解

题目大意

给你一个 N 个点 M 条边的无向带权图，求将这个图变成 K 棵树的最小代价。

主要思路

最小生成树板子题，我们可以用 Kruskal 进行求解。

如果按正常的 Kruskal 全部算完，那么求得是连接成一棵树的最小代价，因为每次合并只会减少一棵树，为了满足此题条件我们就需要在合并 N-K 次时直接结束运算即可。

判断是否存在答案，如果全部运行完后合并的次数小于 N-K，那么就不存在答案。

注意：数据没有保证 K \le N 所以需要特判。

AC Code

#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#ifdef ONLINE_JUDGE
#define getchar getchar_unlocked
#endif
template<typename T> void read(T &x) { int f = 1; x = 0; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-')f = -1; ch = getchar(); }while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }x *= f; }
template<typename T, typename ...Args> void read(T &x, Args &...args) { read(x); read(args...); }
template<typename T> void print(T x) { if (x < 0) { putchar('-'); x = -x; }if (x > 9) { print(x / 10); }putchar(char(x % 10 + 48)); }
template<typename T, typename ...Args> void print(T x, Args ...args) { print(x); putchar(' '); print(args...); }

typedef long long ll;
typedef long double db;
const int N = 1e3 + 10;
const int M = 1e4 + 10;
const int INT_INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
template<typename T1, typename T2> ll _pow(T1 a, T2 b) { ll x = 1, y = a; while(b > 0) {if (b & 1) x *= y; y *= y; b >>= 1; } return x; }
// ----------------------------
struct node {
    int u, v, w;
};
// ----------------------------
int fa[N];
node edge[M];
// ----------------------------
bool cmp(node a, node b) {
    return a.w < b.w;
}

int _find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = _find(fa[x]);
}

void _merge(int x, int y) {
    fa[_find(x)] = _find(y);
}

int main() {
    int n, m, k; read(n, m, k);
    if (k > n) {
        cout << "No Answer";
        return 0;
    }
    for (int i = 1; i <= m; i++) read(edge[i].u, edge[i].v, edge[i].w);
    // ----------------------------
    sort(edge + 1, edge + m + 1, cmp);
    for (int i = 1; i <= n; i++) fa[i] = i;
    int cnt = 0, sum = 0;
    for (int i = 1; i <= m; i++) {
        if (cnt == n - k) break;
        if (_find(edge[i].u) == _find(edge[i].v)) continue;
        cnt++;
        sum += edge[i].w;
        _merge(edge[i].u, edge[i].v);
    }
    // ----------------------------
    if (cnt < n - k) cout << "No Answer";
    else print(sum);
    return 0;
}