P1195

口袋的天空

题目背景

小杉坐在教室里，透过口袋一样的窗户看口袋一样的天空。

有很多云飘在那里，看起来很漂亮，小杉想摘下那样美的几朵云，做成棉花糖。

题目描述

给你云朵的个数 $N$ ，再给你 $M$ 个关系，表示哪些云朵可以连在一起。

现在小杉要把所有云朵连成 $K$ 个棉花糖，一个棉花糖最少要用掉一朵云，小杉想知道他怎么连，花费的代价最小。

输入格式

第一行有三个数 $N,M,K$ 。

接下来 $M$ 行每行三个数 $X,Y,L$ ，表示 $X$ 云和 $Y$ 云可以通过 $L$ 的代价连在一起。

输出格式

对每组数据输出一行，仅有一个整数，表示最小的代价。

如果怎么连都连不出 $K$ 个棉花糖，请输出 No Answer。

输入输出样例

输入样例 #1

3 1 2
1 2 1

输出样例 #1

说明/提示

对于 $30\%$ 的数据， $1 \le N \le 100$ ， $1\le M \le 10^3$ ；

对于 $100\%$ 的数据， $1 \le N \le 10^3$ ， $1 \le M \le 10^4$ ， $1 \le K \le 10$ ， $1 \le X,Y \le N$ ， $0 \le L<10^4$ 。

题解

1 篇题解

登录后即可使用 Markdown 发布题解。

YuyiLv.6👑 站长管理员

P1195 口袋的天空题解 Author: Yuyi 题意分析题意很唯美，但本质依然是赤裸裸的图论模型：有 $N$ 朵云（点）和 $M$ 种连接关系（无向边）。我们想要把这些云朵连成恰好 $K$ 个棉花糖（连通块）。每一个棉花糖至少包含一朵云。题目要求我们挑选一些边使得它们连通，并且花费的总代价（边权之和）最小。如果是要把 $N$ 个点连成 $1$ …

点击展开完整题解点击收起题解

2026年8月9日 22:26

P1195 口袋的天空题解

Author: Yuyi

题意分析

题意很唯美，但本质依然是赤裸裸的图论模型：有 $N$ 朵云（点）和 $M$ 种连接关系（无向边）。我们想要把这些云朵连成恰好 $K$ 个棉花糖（连通块）。每一个棉花糖至少包含一朵云。题目要求我们挑选一些边使得它们连通，并且花费的总代价（边权之和）最小。如果是要把 $N$ 个点连成 $1$ 个连通块，那就是我们需要找最小生成树（加 $N-1$ 条边）。如果是要把 $N$ 个点连成 $K$ 个连通块，由于初始状态下每个点自己就是一个连通块（共有 $N$ 个），我们每成功加入一条有效边，连通块的数量就会减少 $1$ 。所以，我们只需要贪心地按照边权从小到大加边，恰好加上 $N - K$ 条边 即可完成目标！

当然，这里有两个无解的坑点需要注意：

如果 $N < K$ ，也就是云朵的总数还没有你要的棉花糖多，哪怕一个棉花糖只用一朵云也做不出来，直接输出 No Answer。
如果我们遍历完了所有的边，发现成功加进去的边数 cnt 依然达不到 $N - K$ ，说明剩下的云朵死活连不上，也做不出恰好 $K$ 个连通块，同样输出 No Answer。

正解推导过程

输入与特判：读入 $N, M, K$ 。如果发现 $N < K$ ，不要犹豫直接输出 No Answer 结束。
Kruskal 排序：要求代价最小，毫无疑问将所有边按权值从小到大排序。
并查集加边：遍历排序好的边。如果两端的点不在同一个连通块里，就把它们合并，累加代价到 ans，同时记录有效加边数的计数器 cnt++。
结束判定：在循环里，只要 cnt 达到了 $N - K$ ，立刻 break 跳出循环。
输出结果：循环结束后，如果 cnt == N - K，说明大功告成，输出 ans；如果不够，说明图不连通的碎片太多，拼不出 $K$ 个棉花糖，输出 No Answer。

正解代码及分析

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
#define lowbit(a) (a)&(-a)
using namespace std;
const int maxn = 10005; // 按照最大边数10000统一开辟
const int mo = 998244353;
const double pi = acos(-1.0);
template <typename T>
inline void read(T &X)
{
    X = 0;int w = 0; char ch = 0;
    while(!isdigit(ch)) {w |= ch == '-' ;ch = getchar();}
    while(isdigit(ch)) X = X * 10 + (ch^48),ch = getchar();
    if(w) X = -X;
}
int n,m,k;
struct Edge
{
    int u,v;
    int w;
}e[maxn];
bool cmp(Edge A,Edge B)
{
    return A.w < B.w;
}
int fa[maxn];
int find(int u)
{
    if(u == fa[u]) return u;
    return fa[u] = find(fa[u]);
}
void solve()
{
    read(n),read(m),read(k);
    rep(i,1,m) read(e[i].u),read(e[i].v),read(e[i].w);
    if(n < k)
    {
        cout << "No Answer" << endl;
        return;
    }
    rep(i,1,n) fa[i] = i;
    sort(e+1,e+1+m,cmp);
    int cnt = 0;
    ll ans = 0;
    rep(i,1,m)
    {
        if(cnt == n-k) break; // 提前达到了目标，直接溜
        int fu = find(e[i].u);
        int fv = find(e[i].v);
        if(fu != fv)
        {
            fa[fu] = fv;
            ans += e[i].w;
            cnt++;
        }
    }
    if(cnt == n-k) cout << ans << endl;
    else cout << "No Answer" << endl;
    return;
}
int main()
{
    int T=1;
//  freopen("mul.in","r",stdin);
//  freopen("mul.out","w",stdout);
//  read(T);
    while(T--) solve();
    return 0;
}

复杂度分析

时间复杂度：读取 $M$ 条边耗时 $O(M)$ 。对 $M$ 条边进行排序耗时 $O(M \log M)$ 。利用路径压缩的并查集判断连通性，单次查询接近 $O(1)$ ，最多遍历 $M$ 条边，耗时 $O(M)$ 。因此整体时间复杂度为 $O(M \log M)$ ，在 $M \le 10^4$ 的极小规模下，毫秒级通过。
空间复杂度：由于需要存储 $M$ 条边的信息以及 $N$ 个点状态，我们将所有主要数组（e, fa）直接利用常数 maxn = 10005 进行开辟，空间耗费极其微小（几百KB级别），完全规避了直接写死数字造成的隐患。空间复杂度 $O(\max(N,M))$ 。

讨论

0 条讨论

登录后即可使用 Markdown 发起讨论和回复。

还没有讨论，来发起第一条吧。