P2121

拆地毯

题目背景

还记得 NOIP 2011 提高组 Day1 中的铺地毯吗？时光飞逝，光阴荏苒，三年过去了。组织者精心准备的颁奖典礼早已结束，留下的则是被人们踩过的地毯。请你来解决类似于铺地毯的另一个问题。

题目描述

会场上有 $n$ 个关键区域，不同的关键区域由 $m$ 条无向地毯彼此连接。每条地毯可由三个整数 $u$ 、 $v$ 、 $w$ 表示，其中 $u$ 和 $v$ 为地毯连接的两个关键区域编号， $w$ 为这条地毯的美丽度。

由于颁奖典礼已经结束，铺过的地毯不得不拆除。为了贯彻勤俭节约的原则，组织者被要求只能保留至多 $K$ 条地毯，且保留的地毯构成的图中，任意可互相到达的两点间只能有一种方式互相到达。换言之，组织者要求新图中不能有环。现在组织者求助你，想请你帮忙算出这至多 $K$ 条地毯的美丽度之和最大为多少。

输入格式

第一行包含三个正整数 $n$ 、 $m$ 、 $K$ 。

接下来 $m$ 行中每行包含三个正整数 $u$ 、 $v$ 、 $w$ 。

输出格式

只包含一个正整数，表示这 $K$ 条地毯的美丽度之和的最大值。

输入输出样例

输入样例 #1

输出样例 #1

说明/提示

选择第 $1$ 、 $2$ 、 $4$ 条地毯，美丽度之和为 $10 + 9 + 3 = 22$ 。

若选择第 $1$ 、 $2$ 、 $3$ 条地毯，虽然美丽度之和可以达到 $10 + 9 + 7 = 26$ ，但这将导致关键区域 $1$ 、 $2$ 、 $3$ 构成一个环，这是题目中不允许的。

$1\le n,m,K \le 10^5$ 。

题解

1 篇题解

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

YuyiLv.6👑 站长管理员

P2121 拆地毯题解 Author: Yuyi 题意分析题目给定 $N$ 个点和 $M$ 条带有美丽度（边权）的无向边。组织者要求保留至多 $K$ 条边，并且这 $K$ 条边连起来不能有环，同时要求保留下来的边权之和最大。不能有环，其实就是森林或者树的结构；要边权之和最大，这毫无疑问就是最大生成树（最大生成森林）的模型！由于题目只要求保…

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

2026年8月9日 22:33

P2121 拆地毯题解

Author: Yuyi

题意分析

题目给定 $N$ 个点和 $M$ 条带有美丽度（边权）的无向边。组织者要求保留至多 $K$ 条边，并且这 $K$ 条边连起来不能有环，同时要求保留下来的边权之和最大。不能有环，其实就是森林或者树的结构；要边权之和最大，这毫无疑问就是最大生成树（最大生成森林）的模型！由于题目只要求保留至多 $K$ 条边，而边权都是正数（美丽度），所以我们贪心地能选就选，直到成功选取了 $K$ 条边或者没有合法的边可远为止。

正解推导过程

我们只需对标准的 Kruskal 最小生成树算法稍微反转一下思路即可：

贪心排序：因为要求权值之和最大，我们将所有边按权值从大到小进行排序。
并查集判环：按降序遍历所有的边。每次拿到一条边，用并查集 find 查询两个端点是否已经在同一个连通块内。如果不在，说明加这条边不会构成环，直接把它加入我们的阵容中。
结束条件：设置一个计数器 cnt，每成功加入一条边就 cnt++，并且累加美丽度。当 cnt 达到题目限制的 $K$ 时，说明配额已满，立刻 break，输出答案。

正解代码及分析

#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 = 100005; // 按照最大边数和点数10万统一开辟
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;
    ll 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);
    rep(i,1,n) fa[i] = i;
    sort(e+1,e+1+m,cmp);
    int cnt = 0;
    ll ans = 0;
    rep(i,1,m)
    {
        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 == k) break;
    }
    cout << ans << 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)$ ，在 $10^5$ 的数据规模下运算量仅约为 $1.6 \times 10^6$ ，跑得飞快。
空间复杂度：需要存储 $M$ 条边的信息以及 $N$ 个点的并查集状态。代码严格遵循习惯，直接用常量 maxn = 100005 进行全量开辟，总体内存消耗不到 5MB，绝对安全且杜绝了在数组定义时直接写死数字的问题，空间复杂度为 $O(\max(N, M))$ 。

讨论

0 条讨论

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

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

拆地毯