mst常用性质

用到的定理

简单来说：

切分性质 (Cut Property) 告诉你哪些边 一定要选。

环路性质 (Cycle Property) 告诉你哪些边 一定不要选。

1. 切分性质 (Cut Property) —— 选边的依据 一句话总结： 如果要把图分成两部分，连接这两部分的所有边中，最短的那条边一定在 MST 里。

算法应用 Prim 算法：Prim 算法的每一步，都是把点分成“已访问”和“未访问”两个集合，然后通过切分性质，贪心地选取连接这两个集合的最短边。

定理：在无向图中，两点 $u, v$ 之间所有路径中，瓶颈路（最大边权最小的路径）一定在最小生成树上

2. 环路性质 (Cycle Property) —— 删边的依据一句话总结： 在图中任意一个环中，权值最大的那条边，一定不在 MST 里。详细解释如果在图 $G$ 中存在一个环（Cycle）。那么这个环上权值最大的那条边 $e_{max}$，一定不包含在最小生成树中。(注：如果有多条权值相同的最大边，则至少有一条不包含在 MST 中)。

反证法

除了核心的“切分性质”和“环路性质”，MST 还有几个在算法竞赛（CP）中非常实用的性质和定理。掌握这些，能帮你秒杀一些看似复杂的变种题，或者在做题时快速排除错误思路。

以下是 5 个最有用的实战性质：

---

1. 权值集合唯一性 (Weight Set Invariance) —— 计数题的神器

定理内容：

在一个图中，尽管最小生成树可能不唯一（当存在相同权值的边时），但所有可能的最小生成树中，某种权值的边的数量是固定的。

通俗解释：

假设在这个图的一个 MST 里，有 3 条权值为 2 的边，5 条权值为 3 的边。那么，在这个图生成的任何一个其他 MST 里，也一定恰好有 3 条权值为 2 的边，5 条权值为 3 的边。

实战用途：

• 求 MST 的方案数：题目让你求这个图有多少种不同的 MST。
• 解法：由于同权值的边数量固定，我们可以把所有边按权值分组。对于每一组权值（比如权值为 $w$ 的所有边），我们单独计算在不破坏连通性的前提下，有多少种选法能选出固定数量的边。最后根据乘法原理相乘。

---

2. 瓶颈路性质 (Minimax / Bottleneck Property) —— 必考

定理内容：

在无向图中，从 $u$ 到 $v$ 的所有路径中，最大边权最小的那条路径，一定完全由 MST 上的边构成。

数学表达：

定义 $Path(u, v)$ 为 $u$ 到 $v$ 的一条路径，$MaxEdge(P)$ 为路径 $P$ 上的最大边权。

则：$\min \{ MaxEdge(P) \mid P \in \text{all paths between } u, v \} = MaxEdge(\text{path in MST})$。

实战用途：

• 货车运输 / 流量限制 / 噪音限制：题目问“从 A 到 B 运货，车辆限重是多少（经过的桥承重最小）？” 或者 “从 A 到 B 怎么走，使得路上的最大噪音最小？”
• 解法：直接求 MST，然后在 MST 上跑 LCA 求路径最大值（或者用 Kruskal 重构树）。你刚才做的 “ZLGG 的传送门” 就是这个性质的直接应用。

---

3. 单调变换不变性 (Monotonic Transformation) —— 迷惑项克星

定理内容：

如果对图中所有边的权值 $w$ 进行一个单调递增的函数变换 $f(w)$（即如果 $a < b$，则 $f(a) < f(b)$），那么新图的最小生成树结构与原图完全相同。

实战用途：

• 题目迷惑你：
  • 题目让你求 $\sum w^2$ 最小的生成树。
  • 题目让你求 $\sum \sqrt{w}$ 最小的生成树。
  • 题目让你求 $\sum (w + 100)$ 最小的生成树。
• 解法：不用管那些平方、开方。直接按原权值 $w$ 跑 MST 即可！因为 $x^2$、$x+C$ 在 $x>0$ 时都是单调递增的，不会改变边的大小排序关系。Kruskal 只看大小关系，不看具体数值。

---

4. 全局最小边必选 (Global Minimum Edge)

定理内容：

图中权值最小的那条边（如果是唯一的），一定在最小生成树中。

推广：

对于任意一个点 $u$，连接 $u$ 的所有边中权值最小的那条边 $(u, v)$，一定在最小生成树中（或者存在于某个 MST 中，如果不唯一）。

实战用途：

• Borůvka 算法的基础：这个算法就是利用这个性质，让每个点都去找自己最短的边，然后收缩合并。
• 验证贪心思路：当你设计一个复杂的贪心策略时，可以用这个性质来检验你的第一步是否合理。

---

5. 子图 MST 性质 (Subgraph MST) —— 分治法的依据

定理内容：

如果我们把图中的点分成若干个连通块，并且求出了每个连通块内部的 MST。那么，全图的 MST 一定包含这些局部 MST 的边（除非构成了环，需利用环路性质剔除）。

更强的推论：

如果我们把边集 $E$ 随机分成两半 $E_1$ 和 $E_2$，分别求出 $E_1$ 的 MST 边集 $T_1$ 和 $E_2$ 的 MST 边集 $T_2$。那么原图的 MST 一定包含在 $T_1 \cup T_2$ 的生成树中。

实战用途：

• 超大规模图处理：当边数 $M$ 特别大，无法一次性读入内存时，可以分批读入，分批做 MST，保留选中的边，最后再把保留下来的边合并做一次 MST。

---

给你的进阶建议：Kruskal 重构树

既然你熟悉 Kruskal，也熟悉 线段树/Treap 等数据结构，并且刚学了 MST 的瓶颈路性质。

强烈建议你下一步学习 Kruskal 重构树 (Kruskal Reconstruction Tree)。

• 这是什么？ 在 Kruskal 算法执行过程中，每次合并两个集合 $(u, v)$ 时，不直接连边，而是新建一个虚拟节点 $ext$，权值为该边的权值，让 $ext$ 成为 $u$ 和 $v$ 的父节点。
• 有什么用？ 它把图的连通性问题和瓶颈路问题转化为了树上问题（LCA、子树查询）。
• 能解决什么题？
  • “查询从点 $u$ 出发，只走权值 $\le K$ 的边，能到达多少个点？”
  • “查询 $u$ 到 $v$ 所有路径中最大边权的最小值”（直接求 LCA 的点权）。

这个数据结构是解决 Codeforces 高分图论题（2000+分）的利器，非常适合你的技能树。