构造完全图

GitHub跳转原题关系图返回列表

把树边按权值升序做 Kruskal,每次合并两块补 sx*sy-1 条权 w+1 的非树边,累加得最小完全图边权和。

OJ: roj

题目 ID: 1710

难度:普及+/提高-

标签:图论最小生成树并查集Kruskalpython

创建: 2026-10-07 17:32

更新: 2026-10-07 17:32

形式化题目

给定一棵 NN 个点的树 TT,边带正整数权值 DiD_i。在所有"以 TT 为唯一最小生成树"的完全图 GG 中(完全图的边权均为正整数),求 GG 的边权和的最小值。

形式化地说:设完全图 KNK_N 的边集为 EE,每条边赋值 w(e)⩾1w(e) \geqslant 1,要求

  1. T⊆KNT \subseteq K_N,且 TT 的边权就是给定的 DiD_i;
  2. KNK_N 的最小生成树唯一,且恰好等于 TT;

求 ∑e∈Ew(e)\sum_{e \in E} w(e) 的最小值。

正解

思路

完全图有 (N2)\binom{N}{2} 条边,只有 N−1N-1 条被 TT 固定,其余 (N2)−(N−1)\binom{N}{2} - (N-1) 条权值任我们填。问题是这些自由边的权值受一个强约束:填得太小会挤掉 TT 的边,填得太大又白白增大总和。

关键观察:把树边按权值升序排,等价于跑一遍 Kruskal。 因为 TT 是树,Kruskal 处理完 N−1N-1 条树边后所有点恰好连通,每条树边都会被选中。Kruskal 的贪心性质给了我们一条"每步独立决策"的路径。

设当前处理权值为 ww 的树边 (u,v)(u, v),它两端所属的连通块(在只考虑"权值 ⩽w\leqslant w 的树边"时的连通块)大小分别为 sxs_x、sys_y。于是在 KNK_N 中,跨越这两个块的点对共有 sxsys_x s_y 条边。这 sxsys_x s_y 条边里有且仅有 1 条是树边(就是当前的 (u,v)(u, v)),其余 sxsy−1s_x s_y - 1 条都是自由边。

  • 这些自由边必须都 >w> w。若某条自由边权值 <w< w,Kruskal 会先选它而把 (u,v)(u,v) 推到后面,得到的 MST 就不是 TT;若某条自由边权值 =w= w,则 Kruskal 处理到权值 ww 这一批时,uu 侧和 vv 侧会被多条等权边连起来,MST 不唯一。
  • 取到最小可行值 w+1w + 1 即可:此时权值 ww 的边中跨两块的只有 (u,v)(u,v) 一条,它仍会被唯一地选中;而所有权值 >w> w 的自由边都晚于 (u,v)(u,v) 被考虑,不影响选择。权值 w+1w+1 的自由边虽然在"同批"里,但它们连接的是已经被 (u,v)(u,v) 合并成同一块的顶点,不会形成替代方案。

因此这条树边的贡献是

Di+(sxsy−1)(Di+1)D_i + (s_x s_y - 1)(D_i + 1)

其中 DiD_i 是树边自身的权值(它必然出现在完全图里,直接全额计入),后一项是补齐自由边的代价。合并两块后 sx←sx+sys_x \leftarrow s_x + s_y,继续处理下一条树边。所有自由边被划分到唯一的一条树边上(每条自由边连接的两个点,在"合并到某一时刻"分属两块,那一刻恰好被计入一次),无重不漏。

为什么这样得到的就是全局最优? 上面的推理是下界:任意合法完全图中,权值 ww 这条树边对应的 sxsy−1s_x s_y - 1 条跨块自由边都必须 ⩾w+1\geqslant w + 1,贡献不可能比 Di+(sxsy−1)(Di+1)D_i + (s_x s_y-1)(D_i+1) 更小。而我们的构造取等,所以它同时是下界与可达解,即最优。

以题目样例验证:树为 1 ⁣− ⁣2 (1)1\!-\!2\ (1)、1 ⁣− ⁣3 (1)1\!-\!3\ (1)、1 ⁣− ⁣4 (2)1\!-\!4\ (2)。

步骤 树边 合并前两块大小 贡献
1 1 ⁣− ⁣2, w=11\!-\!2,\ w = 1 1×11 \times 1 1+0⋅2=11 + 0 \cdot 2 = 1
2 1 ⁣− ⁣3, w=11\!-\!3,\ w = 1 2×12 \times 1 1+1⋅2=31 + 1 \cdot 2 = 3
3 1 ⁣− ⁣4, w=21\!-\!4,\ w = 2 3×13 \times 1 2+2⋅3=82 + 2 \cdot 3 = 8

合计 1212,与【输出样例】一致,也和【样例说明】里补出的三条边 D(2,3)=2D(2,3)=2、D(3,4)=3D(3,4)=3、D(2,4)=3D(2,4)=3(1+1+2+2+3+3=121+1+2+2+3+3=12)对上。

实现上只需一个按权值排序 + 一个带大小合并的并查集。注意三个细节:答案要用 64 位(最坏 sxsys_x s_y 到 101010^{10} 量级再乘 10510^5,约 5×10145 \times 10^{14});并查集的大小要是"点数"而不是"树边数",因为乘积 sxsys_x s_y 是点对数;N=1N = 1 时没有任何树边,答案为 00,读入循环自然不执行。

代码

Python 短解:

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++ 正式解:

cpp
/**
 * 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;
}

复杂度

排序 O(Nlog⁡N)O(N \log N),并查集 O(N α(N))O(N\,\alpha(N))(路径压缩 + 按大小合并),总时间 O(Nlog⁡N)O(N \log N),空间 O(N)O(N)。N=105N = 10^5 时 C++ 实测不到 0.03s;Python 侧瓶颈在排序与并查集循环,本机 N=105N = 10^5 的测例实测约 0.10s,1s 限时下也安全。

总结

本题的形态是"反 Kruskal":不是从边集里挑出 MST,而是给定 MST 反推一张最小代价的完全图。核心不变量只有一条——按权值升序做 Kruskal 时,每条树边合并两块那一刻,跨两块的 sxsy−1s_x s_y - 1 条非树边必须取 w+1w+1。把它写成式子 Di+(sxsy−1)(Di+1)D_i + (s_x s_y - 1)(D_i + 1) 累加即可。该式的成立依赖"唯一 MST"这个条件(等权边会破坏唯一性,所以自由边只能从 w+1w+1 起取),也依赖 Kruskal 的贪心顺序(每条自由边被唯一分摊到一条树边上)。同型经典题是"走廊泼水节",公式完全一致。

关于本题材料的说明:本仓库该题的 data/ 由 data.py(cyaron)自行生成,题面为网络重建版本(一本通 1710 / LOJ 10067「一本通 3.1 练习 2」构造完全图,样例与原题逐字一致)。生成器包含 N=1N = 1 这一退化用例,此时完全图无边、答案 00,题面未明确提及但可自然推出。素材源 std.cpp 与本解法公式一致,已用真实数据逐点比对确认无误。