From 84a28ab9fd3eb1e83a66804c35cb698a5c81d3c6 Mon Sep 17 00:00:00 2001 From: =?utf8?q?=E5=BF=83=E6=97=B7=E7=A5=9E=E6=80=A1?= Date: Wed, 28 Aug 2019 19:37:15 +0800 Subject: [PATCH] =?utf8?q?=E4=BF=AE=E6=AD=A3=E5=8F=A3=E5=97=A8?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- docs/graph/mst.md | 24 ++++++++++-------------- 1 file changed, 10 insertions(+), 14 deletions(-) diff --git a/docs/graph/mst.md b/docs/graph/mst.md index 84c8ffaa..58cc108f 100644 --- a/docs/graph/mst.md +++ b/docs/graph/mst.md @@ -45,8 +45,6 @@ Kruskal 算法是一种常见并且好写的最小生成树算法，由 Kruskal 抽象一点地说，维护一堆 **集合** ，查询两个元素是否属于同一集合，合并两个集合。 -我们先啥都不管，假设已经实现了这个数据结构…… - 伪代码： $$ @@ -103,8 +101,6 @@ Prim 算法是另一种常见并且好写的最小生成树算法。该算法的 具体来说，每次要选择距离最小的一个结点，以及用新的边更新其他结点的距离。 -等等，这很像 Dijkstra 算法…… - 其实跟 Dijkstra 算法一样，每次找到距离最小的一个点，可以暴力找也可以用堆维护。 堆优化的方式类似 Dijkstra 的堆优化，但如果使用二叉堆等不支持 $O(1)$ decrease-key 的堆，复杂度就不优于 Kruskal，常数也比 Kruskal 大。所以，一般情况下都使用 Kruskal 算法，在稠密图尤其是完全图上，暴力 Prim 的复杂度比 Kruskal 优，但 **不一定** 实际跑得更快。 @@ -493,33 +489,33 @@ int main() { 倍增、树剖都可以解决，这里不再展开。 -## kruskal 重构树 +## Kruskal 重构树 ### 定义 -在跑 kruskal 的过程中我们会从小到大加入若干条边。现在我们仍然按照这个顺序。 +在跑 Kruskal 的过程中我们会从小到大加入若干条边。现在我们仍然按照这个顺序。 首先新建 n 个集合，每个集合恰有一个节点，点权为 $0$ 。 每一次加边会合并两个集合，我们可以新建一个点，点权为加入边的边权，同时将两个集合的根节点分别设为新建点的左儿子和右儿子。然后我们将两个集合和新建点合并成一个集合。将新建点设为根。 -不难发现，在进行 $n-1$ 轮之后我们得到了一棵恰有 $n$ 个叶子的二叉树，同时每个非叶子节点恰好有两个儿子。这棵树就叫 kruskal 重构树。 +不难发现，在进行 $n-1$ 轮之后我们得到了一棵恰有 $n$ 个叶子的二叉树，同时每个非叶子节点恰好有两个儿子。这棵树就叫 Kruskal 重构树。 举个例子： ![](./images/mst5.png) -这张图的 kruskal 重构树如下： +这张图的 Kruskal 重构树如下： ![](./images/mst6.png) ### 性质 -不难发现，最小生成树上两个点之间的简单路径上边权最大值 = kruskal 重构树上两点之间的 LCA 的权值。 +不难发现，最小生成树上两个点之间的简单路径上边权最大值 = Kruskal 重构树上两点之间的 LCA 的权值。 -也就是说，到点 $x$ 的简单路径上边权最大值 $\leq val$ 的所有点 $y$ 均在 kruskal 重构树上的某一棵子树内，且恰好为该子树的所有叶子节点。 +也就是说，到点 $x$ 的简单路径上边权最大值 $\leq val$ 的所有点 $y$ 均在 Kruskal 重构树上的某一棵子树内，且恰好为该子树的所有叶子节点。 -我们在 kruskal 重构树上找到 $x$ 到根的路径上权值 $\leq val$ 的最浅的节点。显然这就是所有满足条件的节点所在的子树的根节点。 +我们在 Kruskal 重构树上找到 $x$ 到根的路径上权值 $\leq val$ 的最浅的节点。显然这就是所有满足条件的节点所在的子树的根节点。 ??? note "[「LOJ 137」最小瓶颈路 加强版](https://loj.ac/problem/137)" @@ -692,11 +688,11 @@ int main() { 我们构造出来根据海拔的最大生成树。显然每次询问可以到达的节点是在最小生成树和询问点的最小边权 $\geq p$ 的节点。 - 根据 kruskal 重构树的性质，这些节点满足均在一棵子树内同时为其所有叶子节点。 + 根据 Kruskal 重构树的性质，这些节点满足均在一棵子树内同时为其所有叶子节点。 - 也就是说，我们只需要求出 kruskal 重构树上每一棵子树叶子的权值 min 就可以支持子树询问。 + 也就是说，我们只需要求出 Kruskal 重构树上每一棵子树叶子的权值 min 就可以支持子树询问。 - 询问的根节点可以使用 kruskal 重构树上倍增的方式求出。 + 询问的根节点可以使用 Kruskal 重构树上倍增的方式求出。 时间复杂度 $O((n+m+Q) \log n)$ -- 2.11.0