把树边按权值升序做 Kruskal,每次合并两块补 sx*sy-1 条权 w+1 的非树边,累加得最小完全图边权和。
OJ: roj
题目 ID: 1710
难度:普及+/提高-
标签:图论最小生成树并查集Kruskalpython
创建: 2026-10-07 17:32
更新: 2026-10-07 17:32
形式化题目
给定一棵
形式化地说:设完全图
,且 的边权就是给定的 ; 的最小生成树唯一,且恰好等于 ;
求
正解
思路
完全图有
关键观察:把树边按权值升序排,等价于跑一遍 Kruskal。 因为
设当前处理权值为
- 这些自由边必须都
。若某条自由边权值 ,Kruskal 会先选它而把 推到后面,得到的 MST 就不是 ;若某条自由边权值 ,则 Kruskal 处理到权值 这一批时, 侧和 侧会被多条等权边连起来,MST 不唯一。 - 取到最小可行值
即可:此时权值 的边中跨两块的只有 一条,它仍会被唯一地选中;而所有权值 的自由边都晚于 被考虑,不影响选择。权值 的自由边虽然在"同批"里,但它们连接的是已经被 合并成同一块的顶点,不会形成替代方案。
因此这条树边的贡献是
其中
为什么这样得到的就是全局最优? 上面的推理是下界:任意合法完全图中,权值
以题目样例验证:树为
| 步骤 | 树边 | 合并前两块大小 | 贡献 |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 |
合计
实现上只需一个按权值排序 + 一个带大小合并的并查集。注意三个细节:答案要用 64 位(最坏
代码
Python 短解:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 17:32
# update_at: 2026-10-07 17:32
import sys
def root(parent: list[int], x: int) -> int:
"""并查集找根,带路径压缩(迭代写法,链深 1e5 也不爆栈)。"""
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def extra_weight(triples: list[tuple[int, int, int]], n: int) -> int:
"""Kruskal 式合并:每条树边 (u,v,w) 合并两块时,补 sx*sy-1 条权 w+1 的非树边。"""
parent = list(range(n + 1))
size = [1] * (n + 1)
total = 0
for w, u, v in sorted((w, u, v) for u, v, w in triples): # 按权值升序,等价于 Kruskal
a, b = root(parent, u), root(parent, v)
# 跨两块 sx*sy 条点对里 1 条已是树边,其余取 w+1 恰好不破坏 MST 的唯一性
total += (size[a] * size[b] - 1) * (w + 1)
if size[a] < size[b]: # 小树挂大树
a, b = b, a
parent[b] = a
size[a] += size[b]
return total
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
triples = [(next(data), next(data), next(data)) for _ in range(n - 1)] # (u, v, w)
print(sum(w for _, _, w in triples) + extra_weight(triples, n)) # 树边全额 + 补齐的非树边
if __name__ == "__main__":
solve()C++ 正式解:
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 17:32
* update_at: 2026-10-07 17:32
*/
// 构造完全图(一本通 1710)
// 给一棵树 T,求以 T 为唯一最小生成树的完全图 G 的最小边权和。
//
// 算法(Kruskal 思想 + 并查集,O(N log N)):
// 把 N-1 条树边按权值 w 从小到大排序,依次用并查集合并两端所在连通块。
// 合并前两块大小分别为 sx、sy,则跨两块的点对共 sx*sy 条:
// 其中 1 条就是当前这条树边(权 w,已计入答案),
// 其余 sx*sy-1 条在完全图里必须 >= w+1,否则最小生成树就不唯一了;
// 取 w+1 时恰好可行(该权值下跨块的唯一最轻边仍是这条树边)。
// 故每条树边贡献 w + (sx*sy-1)*(w+1),合并后 size 相加。
//
// 唯一性论证:Kruskal 按权值升序扫时,处理到权 w 的树边时它两端连通块之间
// 所有非树边权值都 > w(构造取 w+1),所以每条树边都被严格地"抢先"选中,
// 不存在权值相等的替代边,T 是唯一的 MST。
//
// 数据范围:N <= 100000,1 <= D_i <= 100000。
// 答案量级最坏约 n^2/2 * 1e5 ≈ 5e14,超 32 位,全程用 long long。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005; // 点数上限
struct Edge {
ll u; // 端点
ll v; // 端点
ll w; // 边权
};
Edge edge[MAXN]; // N-1 条树边,排序后按权值升序处理
ll fa[MAXN]; // 并查集父亲
ll siz[MAXN]; // 连通块点数:跨块点对数是它俩的乘积,答案里要乘 w+1
ll n; // 点数
ll ans; // 答案:所有树边权值 + 补出来的非树边权值
bool cmp_edge(const Edge &a, const Edge &b) { return a.w < b.w; }
// 并查集找根,带路径压缩(迭代写法,链深 1e5 也不会爆栈)
ll find_root(ll x) {
while (fa[x] != x) {
fa[x] = fa[fa[x]];
x = fa[x];
}
return x;
}
void solve() {
scanf("%lld", &n);
ans = 0;
for (ll i = 1; i <= n - 1; i++) {
scanf("%lld%lld%lld", &edge[i].u, &edge[i].v, &edge[i].w);
ans += edge[i].w; // 树边本身全部出现在完全图里,先全额计入
}
sort(edge + 1, edge + n, cmp_edge); // 注意右端点是 edge+n:只需排前 n-1 条
for (ll i = 1; i <= n; i++) {
fa[i] = i;
siz[i] = 1;
}
for (ll i = 1; i <= n - 1; i++) {
ll a = find_root(edge[i].u);
ll b = find_root(edge[i].v);
ll sx = siz[a];
ll sy = siz[b];
// 跨两块共 sx*sy 条边,扣掉 1 条树边,剩下的每条最少 w+1
ans += (sx * sy - 1) * (edge[i].w + 1);
if (sx < sy) { // 小树挂大树,保证路径压缩的效率
fa[a] = b;
siz[b] = sx + sy;
} else {
fa[b] = a;
siz[a] = sx + sy;
}
}
printf("%lld\n", ans);
}
int main() {
solve();
return 0;
}复杂度
排序
总结
本题的形态是"反 Kruskal":不是从边集里挑出 MST,而是给定 MST 反推一张最小代价的完全图。核心不变量只有一条——按权值升序做 Kruskal 时,每条树边合并两块那一刻,跨两块的
关于本题材料的说明:本仓库该题的
data/由data.py(cyaron)自行生成,题面为网络重建版本(一本通 1710 / LOJ 10067「一本通 3.1 练习 2」构造完全图,样例与原题逐字一致)。生成器包含这一退化用例,此时完全图无边、答案 ,题面未明确提及但可自然推出。素材源 std.cpp与本解法公式一致,已用真实数据逐点比对确认无误。