最小生成树的增量构造与在线最小生成树（Incremental MST）问题
字数 2107 2025-12-12 23:44:36

最小生成树的增量构造与在线最小生成树（Incremental MST）问题

题目描述

假设我们有一个无向连通图，初始时没有边。现在我们需要处理一系列在线的加边操作。每次加边后，我们需要立即得到当前图的最小生成树（Minimum Spanning Tree, MST）的总权重，并能够高效维护这个 MST 的结构。

输入：一个无向图，初始只有 n 个顶点（编号 0 到 n-1），没有边。之后依次给出 m 条边的插入操作，每条边包含三个整数 (u, v, w)，表示在顶点 u 和 v 之间添加一条权重为 w 的边。

输出：每次加边操作后，输出当前图的最小生成树的权重。如果当前图还不连通，则输出 "Disconnected"。

限制：n 可以很大（例如 ≤ 10^5），m 也可能很大（≤ 2×10^5），因此需要每次加边后能快速更新 MST，而不能每次重新计算。

核心思路

这个问题实际上是一个动态图 MST 维护问题，但这里的动态只包含“加边”操作（是增量构造），不包含删边。
我们可以利用这样一个性质：如果当前图已经有了一个 MST，新加入一条边 e 后，新的 MST 的边集要么不变，要么是原 MST 的边集加上 e，然后删去原 MST 中形成的环里的最大权重边。

步骤 1：初始状态

初始时，图是 n 个孤立顶点，没有边。MST 不存在，总权重为 0，但图不连通，所以输出 "Disconnected"。

步骤 2：维护数据结构

我们需要：

  1. 一个能表示当前 MST 的树结构，并支持快速查询树上两点之间的最大边权重。
  2. 当新边加入时，判断是否加入 MST 并更新。

具体选择：

  • 用并查集维护连通性（如果当前 MST 不包含所有顶点，则图不连通）。
  • 用动态树（Link-Cut Tree, LCT） 来维护当前 MST 树，它能支持在 O(log n) 时间内查询树上任意两点间的最大权重边，并支持删掉最大边、加入新边。

步骤 3：增量更新 MST 的规则

设当前图是 G，当前 MST 是 T，新边是 e=(u,v,w)。

情况 1：u 和 v 在当前 T 中不连通（即整个图原本不连通，或者这两个分量在 T 中没有边连接）。
这时，加入 e 会连接两个连通分量，那么直接将 e 加入 MST 即可，不会形成环。
更新：T = T ∪ {e}。

情况 2：u 和 v 已经在 T 中连通。
那么在 T 中 u 到 v 的路径上，找到最大权重的边 e_max。

  • 如果 w < weight(e_max)，则 e 比 e_max 更优，用 e 替换 e_max，新的 MST 总权重减少 weight(e_max)-w。
  • 如果 w ≥ weight(e_max)，则 MST 不变。

步骤 4：连通性判断

即使 T 是当前 MST，它也可能没有连接所有顶点（当图还不连通时）。
我们用并查集维护实际连通性（不仅是 T 中的连通性，因为可能有非树边连接分量）。
每次加边 (u,v,w)，先用并查集检查 u 和 v 是否连通，以此判断是否连接了两个不同连通分量。

  • 如果不连通，加入 e 后，图可能还是不一定全连通，但至少 u 和 v 所在的分量合二为一。
    此时直接将 e 加入 T，并更新并查集。
  • 如果连通，走情况 2 的判断替换步骤。

步骤 5：算法流程

初始化：
    parent[n] 为并查集
    T 为空（用 LCT 表示）
    total_weight = 0
    components = n  // 当前连通分量个数

对每条新边 e = (u, v, w)：
    如果 components > 1：
        如果 find(u) != find(v)：
            将 e 插入 LCT 的 T 中
            union(u, v)
            total_weight += w
            components -= 1
        否则：
            // u, v 已连通
            在 T 中查询 u-v 路径上的最大边 e_max
            如果 w < weight(e_max)：
                从 T 中删掉 e_max
                在 T 中加入 e
                total_weight += w - weight(e_max)
    否则（components == 1，图已连通）：
        在 T 中查询 u-v 路径上的最大边 e_max
        如果 w < weight(e_max)：
            从 T 中删掉 e_max
            在 T 中加入 e
            total_weight += w - weight(e_max)
    
    如果 components == 1：
        输出 total_weight
    否则：
        输出 "Disconnected"

步骤 6：LCT 如何维护最大边

LCT 的每个节点代表一条边（也可以将边转化为点，常用技巧：将边看作一个新节点连接 u 和 v）。
每个节点维护子树中最大权重边的信息。
支持操作：

  • link(x, y)：连接两个节点
  • cut(x, y)：断开边
  • query_max(u, v)：查询 u-v 路径上的最大权重边

实现时，将边 (u,v,w) 表示为一个新节点 p，权重为 w，然后连接 p-u 和 p-v。

步骤 7：复杂度分析

  • 每次操作：O(log n)（LCT 操作时间）。
  • 总体 O((n+m) log n)。
  • 可以处理 n,m 达到 10^5 数量级。

步骤 8：简单例子

n=3，初始 3 个孤立点，components=3，total=0，T 为空。

  1. 加边 (0,1,4)：
    0 和 1 不连通 → 加入 T，total=4，components=2，输出 "Disconnected"。

  2. 加边 (1,2,3)：
    1 和 2 不连通 → 加入 T，total=7，components=1，输出 7。

  3. 加边 (0,2,5)：
    已连通，原 MST 中 0-2 路径是 0-1(4) 和 1-2(3)，最大权重边是 4。
    5>4，不替换，total=7，输出 7。

  4. 加边 (0,2,2)：
    已连通，原路径上最大权重边是 4，2<4，替换 4 的边，
    total = 7 - 4 + 2 = 5，输出 5。

小结

这个算法是在线 MST 维护的经典方法，利用“环中最大边替换”的性质，借助动态树快速更新。它只适用于加边操作，对于删边则需要更复杂的数据结构（动态 MST 完全体）。

最小生成树的增量构造与在线最小生成树（Incremental MST）问题 题目描述 假设我们有一个 无向连通图 ，初始时没有边。现在我们需要处理一系列 在线 的加边操作。每次加边后，我们需要立即得到当前图的最小生成树（Minimum Spanning Tree, MST）的总权重，并能够高效维护这个 MST 的结构。 输入 ：一个无向图，初始只有 n 个顶点（编号 0 到 n-1），没有边。之后依次给出 m 条边的插入操作，每条边包含三个整数 (u, v, w)，表示在顶点 u 和 v 之间添加一条权重为 w 的边。 输出 ：每次加边操作后，输出当前图的最小生成树的权重。如果当前图还不连通，则输出 "Disconnected"。 限制 ：n 可以很大（例如 ≤ 10^5），m 也可能很大（≤ 2×10^5），因此需要每次加边后能快速更新 MST，而不能每次重新计算。 核心思路 这个问题实际上是一个 动态图 MST 维护 问题，但这里的动态只包含“加边”操作（是 增量构造 ），不包含删边。 我们可以利用这样一个性质： 如果当前图已经有了一个 MST，新加入一条边 e 后，新的 MST 的边集要么不变，要么是原 MST 的边集加上 e，然后删去原 MST 中形成的环里的最大权重边 。 步骤 1：初始状态 初始时，图是 n 个孤立顶点，没有边。MST 不存在，总权重为 0，但图不连通，所以输出 "Disconnected"。 步骤 2：维护数据结构 我们需要： 一个能表示当前 MST 的树结构，并支持快速查询树上两点之间的最大边权重。 当新边加入时，判断是否加入 MST 并更新。 具体选择 ： 用 并查集 维护连通性（如果当前 MST 不包含所有顶点，则图不连通）。 用 动态树（Link-Cut Tree, LCT） 来维护当前 MST 树，它能支持在 O(log n) 时间内查询树上任意两点间的最大权重边，并支持删掉最大边、加入新边。 步骤 3：增量更新 MST 的规则 设当前图是 G，当前 MST 是 T，新边是 e=(u,v,w)。 情况 1 ：u 和 v 在当前 T 中不连通（即整个图原本不连通，或者这两个分量在 T 中没有边连接）。 这时，加入 e 会连接两个连通分量，那么直接将 e 加入 MST 即可，不会形成环。 更新：T = T ∪ {e}。 情况 2 ：u 和 v 已经在 T 中连通。 那么在 T 中 u 到 v 的路径上，找到最大权重的边 e_ max。 如果 w < weight(e_ max)，则 e 比 e_ max 更优，用 e 替换 e_ max，新的 MST 总权重减少 weight(e_ max)-w。 如果 w ≥ weight(e_ max)，则 MST 不变。 步骤 4：连通性判断 即使 T 是当前 MST，它也可能没有连接所有顶点（当图还不连通时）。 我们用并查集维护实际连通性（不仅是 T 中的连通性，因为可能有非树边连接分量）。 每次加边 (u,v,w)，先用并查集检查 u 和 v 是否连通，以此判断是否连接了两个不同连通分量。 如果不连通，加入 e 后，图可能还是不一定全连通，但至少 u 和 v 所在的分量合二为一。 此时直接将 e 加入 T，并更新并查集。 如果连通，走情况 2 的判断替换步骤。 步骤 5：算法流程 步骤 6：LCT 如何维护最大边 LCT 的每个节点代表一条边（也可以将边转化为点，常用技巧：将边看作一个新节点连接 u 和 v）。 每个节点维护子树中最大权重边的信息。 支持操作： link(x, y) ：连接两个节点 cut(x, y) ：断开边 query_max(u, v) ：查询 u-v 路径上的最大权重边 实现时，将边 (u,v,w) 表示为一个新节点 p，权重为 w，然后连接 p-u 和 p-v。 步骤 7：复杂度分析 每次操作：O(log n)（LCT 操作时间）。 总体 O((n+m) log n)。 可以处理 n,m 达到 10^5 数量级。 步骤 8：简单例子 n=3，初始 3 个孤立点，components=3，total=0，T 为空。 加边 (0,1,4)： 0 和 1 不连通 → 加入 T，total=4，components=2，输出 "Disconnected"。 加边 (1,2,3)： 1 和 2 不连通 → 加入 T，total=7，components=1，输出 7。 加边 (0,2,5)： 已连通，原 MST 中 0-2 路径是 0-1(4) 和 1-2(3)，最大权重边是 4。 5>4，不替换，total=7，输出 7。 加边 (0,2,2)： 已连通，原路径上最大权重边是 4，2 <4，替换 4 的边， total = 7 - 4 + 2 = 5，输出 5。 小结 这个算法是 在线 MST 维护 的经典方法，利用“环中最大边替换”的性质，借助动态树快速更新。它只适用于加边操作，对于删边则需要更复杂的数据结构（动态 MST 完全体）。