Home Explore Help
Sign In
wfirstzhang
/
lessons
mirror of https://gitee.com/wfz7789/noip_lessons.git
1
0
Fork 0
Files Issues 0 Wiki
Tree: 52bd18832a
Branches Tags
lessons
/
课程
/
06-最小与最大生成树
/
01-割性质与隐式完全图建模.md

01-割性质与隐式完全图建模.md 8.5 KB
History Raw

最小生成树：割性质、Kruskal 与隐式完全图

若还没有把“连通块合并”和割性质连起来，先完成 课前零食：只修够用的路。

本节目标

学完后，你应能证明 Kruskal/Prim，使用割性质安全削减完全图候选边，并用超级源把“选设施或连线”统一成生成树。

前置知识与课前自测

前置：并查集、排序、连通图。

  1. 当前森林的两个连通块之间，最轻边为什么可以安全加入某棵 MST？
  2. Kruskal 遇到同权边时任选会影响总权吗？会影响树的唯一性吗？
  3. 有 $10^5$ 点的完全图能否显式生成全部边再排序？
自测答案 1. 这条边跨越某个割；用它替换任一 MST 跨该割的边不会更重。 2. 不影响最小总权，但可能得到不同 MST；唯一性需单独分析。 3. 不能，边数 $O(n^2)$；必须证明只保留稀疏候选仍覆盖每个割的足够轻边。

问题动机与核心知识

最小生成树（Minimum Spanning Tree, MST）连接全部点、无环且边权和最小。两条互补性质是：

  • 割性质：任意割上的最轻边至少属于一棵 MST；若严格最轻，则属于每棵 MST。
  • 环性质：环上严格最重边不属于任何 MST。

Kruskal 按权从小到大，只在两个不同并查集间加边；每步用割性质安全扩展。Prim 则维护已选点集与外界的最轻边，同样是割性质。两者区别主要是图的表示：稀疏边表适合 Kruskal，能按需计算点到集合代价的稠密图常适合 $O(n^2)$ Prim。

实现指南

  • 总权可能达到 $(n-1)\times10^{18}$ 量级，按题面选择 long long 或更宽类型。
  • Kruskal 的同权批次若涉及唯一性/边分类，不能一条条立即合并；基础求权时才可任选。
  • 隐式图删边必须给割性质证明，“看起来最近”不够。
  • 输出构造时记录实际被选边，而不是事后仅由父数组猜测。

精选例题 1：Built?

来源信息与题意

$2\le N\le10^5$ 个平面城镇，坐标至 $10^9$，可连接任意两城，费用为 $\min(|x_i-x_j|,|y_i-y_j|)$。求连通全部城镇的最小费用。

Hint 1分别按 $x$、$y$ 排序，只保留相邻点对。
Hint 2证明要针对任意割：取割上最便宜完整边，并看实现其费用的那个坐标。
Hint 3沿该坐标排序，从割的一侧走到另一侧，必遇到一对相邻跨割点，其费用不更大。

Observations、Editorial 与证明

按 $x$ 排序加入相邻对，按 $y$ 再加入相邻对，共 $O(N)$ 条候选边。对完整图任一割，取最轻跨割边 $(u,v)$，设其费用由 $x$ 差实现。沿 $x$ 排序从 $u$ 到 $v$ 的区间中必有一对相邻点跨该割，坐标差不超过 $|x_u-x_v|$，其真实费用又不超过坐标差。因此候选图在每个割上都含一条不比完整图最轻边更重的边，Kruskal 可得到同样最优权。

复杂度 $O(N\log N)$，空间 $O(N)$。

核心伪代码与参考实现附件

candidates = []
sort towns by x; add every adjacent pair
sort towns by y; add every adjacent pair
give each candidate its true min(|dx|, |dy|) cost
output Kruskal(candidates)

完整 GNU C++17 参考实现见附件：AtCoder-arc076_b.cpp

复盘与变式

若费用改成 Manhattan 距离，单纯保留 $x/y$ 相邻边不再成立；需使用按象限变换的候选边生成等不同工具。

精选例题 2：Shichikuji and Power Grid

来源信息与题意

$n\le2000$ 个城市。城市 $i$ 建电站花 $c_i$；连接 $i,j$ 花 $(k_i+k_j)(|x_i-x_j|+|y_i-y_j|)$。每城需建站或经电线连到有电城市，求最小费用并输出电站与电线。

Hint 1新增超级源 0，边 $0-i$ 的费用为 $c_i$；选这条边表示在 $i$ 建站。
Hint 2其余城市间边就是电线。目标变成 $n+1$ 点图的 MST。
Hint 3边数约两百万，可不显式存边，用 $O(n^2)$ Prim 动态计算。

Observations、Editorial 与证明

任何供电方案的每个连通电网至少有一个电站；把每座电站连到超级源后得到连通图，可删环而不增费用成为生成树。反之超级源 MST 去掉源后，每个分量恰通过至少一条站边获电。因此方案与生成树最优值一致。

先把每城到当前树的最小费用初始化为建站费用，父亲记为 -1。每次加入最便宜城市，再用它到其余城市的电线费用更新。父亲 -1 表示电站，否则输出电线。复杂度 $O(n^2)$，空间 $O(n)$。

核心伪代码与参考实现附件

treat building station i as edge super_source-i with cost c[i]
initialize Prim key[i] = c[i], parent[i] = super_source
repeat n times:
    select unused city v with minimum key
    record station if parent is source, otherwise record wire
    update every unused city's key by wire_cost(v, city)
output total and recorded construction

完整 GNU C++17 参考实现见附件：CodeForces-1245D.cpp

复盘与变式

若规定恰建 $K$ 座电站，就不再是普通 MST；可考虑给站边统一加参数做 WQS 二分，但需要证明站数随参数单调。

精选例题 3：Make It Connected

来源信息与题意

$n,m\le2\times10^5$。任意两点 $x,y$ 可花 $a_x+a_y$ 连边，另有 $m$ 条指定优惠边。求连通全部点的最小费用，$a_i,w\le10^{12}$。

Hint 1找 $a$ 最小的顶点 $p$，只保留普通边 $(p,v)$。
Hint 2任意割上，若 $p$ 在一侧，跨割最便宜普通边一定可以选 $p$ 到另一侧 $a$ 最小点。
Hint 3把这些 $n-1$ 条普通边与全部优惠边一起 Kruskal。

Observations、Editorial 与证明

对任意割，设全局最小点 $p$ 在左侧，右侧普通边最便宜端点为 $v$。边 $(p,v)$ 的费用不大于任意普通跨割边。因此星形候选保留了每个割最便宜的普通选择；优惠边全部保留后，候选图足以由割性质得到原问题 MST。

边数降到 $m+n-1$，复杂度 $O((n+m)\log(n+m))$。

核心伪代码与参考实现附件

hub = vertex with minimum a[hub]
candidates = all special offers
for every v != hub: add ordinary edge hub-v with cost a[hub]+a[v]
output Kruskal(candidates)

完整 GNU C++17 参考实现见附件：CodeForces-1095F.cpp

复盘与变式

本题能削成星是因为普通边权可分离为 $a_x+a_y$。若是 $a_xa_y$ 且含负数，或附加距离项，割上的最便宜端点结构会改变。

扩展与联系

  • 最大生成树只需反向排序；割/环性质中的“轻/重”对应互换。
  • 瓶颈最小生成树最小化树中最大边，任一 MST 都达到最优瓶颈，但反命题不成立。
  • 超级源还能表达“从若干设施任选一个接入”；是否能用 MST 取决于总代价能否写成所选边之和。

总结与自检

  1. 割性质与环性质分别怎样证明？
  2. Built? 为什么只保留坐标相邻边仍覆盖每个割？
  3. 电站题中超级源边的选择语义是什么？
  4. Make It Connected 的星形削边依赖哪种可分离结构？

课后训练建议

先手写 Kruskal 并与枚举生成树对拍小图。三题都要求先写“任意割上保留了什么边”的证明再编码；做完后改变费用公式，主动构造候选边削减失效的最小反例。