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

> 若还没有把“连通块合并”和割性质连起来，先完成 [课前零食：只修够用的路](00-课前零食-只修够用的路.md)。

## 本节目标

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

## 前置知识与课前自测

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

1. 当前森林的两个连通块之间，最轻边为什么可以安全加入某棵 MST？
2. Kruskal 遇到同权边时任选会影响总权吗？会影响树的唯一性吗？
3. 有 $10^5$ 点的完全图能否显式生成全部边再排序？

<details><summary>自测答案</summary>

1. 这条边跨越某个割；用它替换任一 MST 跨该割的边不会更重。
2. 不影响最小总权，但可能得到不同 MST；唯一性需单独分析。
3. 不能，边数 $O(n^2)$；必须证明只保留稀疏候选仍覆盖每个割的足够轻边。

</details>

## 问题动机与核心知识

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

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

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

## 实现指南

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

## 精选例题 1：Built?

### 来源信息与题意

- VJudge：[AtCoder-arc076_b Built?](https://vjudge.net/problem/AtCoder-arc076_b)
- 原题：[AtCoder ABC065 D / ARC076 B](https://atcoder.jp/contests/abc065/tasks/arc076_b)
- 大致难度：提高；考点：完全图候选边削减、Kruskal

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

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

### Observations、Editorial 与证明

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

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

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

```text
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](../../参考实现/06-最小与最大生成树/AtCoder-arc076_b.cpp)

### 复盘与变式

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

## 精选例题 2：Shichikuji and Power Grid

### 来源信息与题意

- VJudge：[CodeForces-1245D Shichikuji and Power Grid](https://vjudge.net/problem/CodeForces-1245D)
- 原题：[Codeforces Round 597 (Div. 2)](https://codeforces.com/problemset/problem/1245/D)
- 难度：1900；考点：超级源、稠密 Prim、方案输出

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

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

### Observations、Editorial 与证明

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

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

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

```text
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](../../参考实现/06-最小与最大生成树/CodeForces-1245D.cpp)

### 复盘与变式

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

## 精选例题 3：Make It Connected

### 来源信息与题意

- VJudge：[CodeForces-1095F Make It Connected](https://vjudge.net/problem/CodeForces-1095F)
- 原题：[Codeforces Round 529 (Div. 3)](https://codeforces.com/problemset/problem/1095/F)
- 难度：1900；考点：隐式边削减、特殊优惠与 Kruskal

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

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

### Observations、Editorial 与证明

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

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

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

```text
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](../../参考实现/06-最小与最大生成树/CodeForces-1095F.cpp)

### 复盘与变式

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

## 扩展与联系

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

## 总结与自检

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

## 课后训练建议

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