最小生成树 · 建模与选型

本篇用作建模速查与复习；第一次学习 Kruskal，先读《最小生成树 (MST)：Kruskal 算法与 Prim 简介》，再回来比较算法、练模型迁移。

一、最小生成树定义

在一张包含 $n$ 个节点和 $m$ 条边的无向连通图中，若选出其中的 $n-1$ 条边将所有节点连通且不构成环，构成的子图称为原图的生成树 (Spanning Tree)。若边的权值之和最小，则该树称为最小生成树（Minimum Spanning Tree, MST）。

对于树以及最小生成树，记住下面几个特征：

• 边的数量恒定：任意包含 $n$ 个节点的树，必须且只能拥有 $n-1$ 条边。
• 连通且无环：添加任意一条非树边必然产生唯一简单环；删除任意一条树边必然导致图不连通。
• 形态非唯一，权值必唯一：当图中存在多条权值相同的边时，最小生成树的拓扑形态可能不唯一，但所有最小生成树的边权总和必然是完全一致且唯一的。

flowchart LR
    subgraph Raw ["原加权无向连通图 G (含环)"]
        direction TB
        r1((1)) --- |"1"| r2((2))
        r2 --- |"2"| r3((3))
        r3 --- |"4"| r4((4))
        r4 --- |"3"| r1
        r1 --- |"5"| r3
    end

    subgraph MST ["最小生成树 T (n个点, n-1条边, 无环且权值和最小)"]
        direction TB
        m1((1)) === |"1"| m2((2))
        m2 === |"2"| m3((3))
        m1 === |"3"| m4((4))
        m3 -.- |"舍弃冗余高权边"| m4
        m1 -.- |"舍弃对角高权边"| m3
    end

    Raw --> |"贪心剔除高权环边<br/>保留骨干网络"| MST

    style Raw fill:#f7fafc,stroke:#a0aec0,stroke-width:1px
    style MST fill:#f0fff4,stroke:#38a169,stroke-width:2px
    style m1 fill:#c6f6d5,stroke:#22543d
    style m2 fill:#c6f6d5,stroke:#22543d
    style m3 fill:#c6f6d5,stroke:#22543d
    style m4 fill:#c6f6d5,stroke:#22543d
    linkStyle 5 stroke:#38a169,stroke-width:3px
    linkStyle 6 stroke:#38a169,stroke-width:3px
    linkStyle 7 stroke:#38a169,stroke-width:3px
    linkStyle 8 stroke:#e53e3e,stroke-width:1px,stroke-dasharray: 3 3
    linkStyle 9 stroke:#e53e3e,stroke-width:1px,stroke-dasharray: 3 3

二、Kruskal 算法：加边贪心与并查集判环

适用场景：稀疏图（$m \ll n^2$，如 $m \approx n$）。
时间复杂度：主要取决于边排序，为 $O(m \log m)$；并查集单次查询均摊 $O(\alpha(n))$，可视为极小常数。

下面另用一个独立的五点七边例子演示 Kruskal：按权值考察各边，跳过成环的边，最终选出四条边，总权值为 12。

1. 算法流程

1. 全局排序：将图中的所有 $m$ 条边按权值 $w$ 从小到大升序排序。
2. 集合初始化：建立并查集，初始化每个节点自成一个独立的连通分量（$n$ 棵孤立单点树）。
3. 贪心考察与判环：从权值最小的边开始依次考察 $(u, v, w)$：
   • 用并查集判断两端点连通性：若 find(u) == find(v)，说明两点已经在同一连通块内，强行加入必定产生闭环回路，必须直接放弃。
   • 若 find(u) != find(v)，说明加入该边安全无环，执行合并（fa[find(u)] = find(v)），并将该边权值计入答案，已选边数计数器 cnt++。
4. 提前剪枝与无解判定：
   • 当选入的边数累计达到 $n - 1$ 条 时，全图已彻底连通，立刻提前终止循环 (break)。
   • 若遍历完所有 $m$ 条边后，累计边数仍然不足 $n - 1$ 条，说明原图本身存在多个不连通的分支，无法形成生成树，输出无解标识（如 orz）。

flowchart TD
    Start(["开始"]) --> Sort["将全图所有 m 条边按权值升序排序"]
    Sort --> Init["初始化并查集：fa[i] = i<br/>计数器 cnt = 0，总权值 ans = 0"]
    Init --> Loop{"还有未遍历的边？"}
    
    Loop -- 否 --> CheckFinal{"cnt == n - 1 ?"}
    Loop -- 是 --> Pick["取出当前权值最小的边 (u, v, w)"]
    
    Pick --> Check{"find(u) == find(v) ?"}
    Check -- 是 (同属同一集合) --> Drop["已在同一连通块<br/>加入会成环，直接舍弃"] --> Loop
    Check -- 否 (处于不同集合) --> Merge["合并集合：fa[find(u)] = find(v)<br/>ans += w<br/>cnt++"]
    
    Merge --> CheckCnt{"cnt == n - 1 ?"}
    CheckCnt -- 是 --> Success(["提前剪枝退出，输出 ans"])
    CheckCnt -- 否 --> Loop
    
    CheckFinal -- 是 --> Success
    CheckFinal -- 否 --> Fail(["全图不连通，输出 orz"])

    style Start fill:#edf2f7,stroke:#4a5568
    style Success fill:#c6f6d5,stroke:#22543d,stroke-width:2px
    style Fail fill:#fed7d7,stroke:#9b2c2c,stroke-width:2px
    style Merge fill:#ebf8ff,stroke:#3182ce
    style Drop fill:#fffaf0,stroke:#dd6b20

2. 标准模板实现 (洛谷 P3366，复习)

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5005;    // 点数上限
const int M = 200005;  // 边数上限

// 边集结构体定义
struct Edge {
    int u, v, w;
} e[M];

int fa[N]; // 并查集父节点数组

// 排序比较规则：按边权升序排列
bool cmp(Edge x, Edge y) {
    return x.w < y.w;
}

// 并查集路径压缩：递归将沿途节点全部直接挂载到根节点
int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

void solve() {
    int n, m;
    cin >> n >> m;
    
    // 1. 初始化并查集
    for (int i = 1; i <= n; i++) fa[i] = i;
    
    // 2. 读入边集
    for (int i = 1; i <= m; i++) {
        cin >> e[i].u >> e[i].v >> e[i].w;
    }
    
    // 3. 全局按边权升序排序
    sort(e + 1, e + m + 1, cmp);
    
    int cnt = 0; // 记录已成功加入生成树的边数
    int ans = 0; // 累计最小生成树的边权总和
    
    // 4. 贪心扫描每条边
    for (int i = 1; i <= m; i++) {
        int fu = find(e[i].u);
        int fv = find(e[i].v);
        
        // 若两端点不属于同一集合，说明不会产生回路
        if (fu != fv) {
            fa[fu] = fv;      // 合并两个连通块
            ans += e[i].w;    // 累加边权
            cnt++;            // 树边数 +1
            
            // 剪枝：选够 n - 1 条边说明全图已连通，提前退出
            if (cnt == n - 1) break;
        }
    }
    
    // 5. 连通性校验：若刚好选入 n - 1 条边则合法，否则图不连通
    if (cnt == n - 1) cout << ans << "\n";
    else cout << "orz\n";
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}

三、Prim 算法：加点贪心与切分推进

适用场景：极稠密图（$m \approx n^2$）或完全图。
核心思想：“加点法” / 领地扩张。从单点种子开始，滚雪球式生长成整棵树。
时间复杂度：

• 堆优化版（优先队列 + 邻接表）：$O(m \log n)$。
• 朴素版（暴力扫描 + 邻接矩阵）：$O(n^2)$。在 $n \le 2000$ 且边数逼近 $n^2$ 的稠密图中，朴素 Prim 的速度甚至碾压所有带 $\log$ 的算法。

1. 算法流程

1. 定种子：任选一个节点（通常为 1 号点）加入已选集合 $S$（生成树领地），令其到树的距离 dist[1] = 0；其余节点属于未选集合 $V \setminus S$，距离初始化为正无穷。
2. 割边寻优：在所有“一端在集合 $S$ 内、一端在集合 $S$ 外”的割边中，贪心挑选权值最小的那条边。
3. 吸纳入树：将该边连接的外部节点拉入集合 $S$，累加其边权。
4. 状态松弛：利用新加入的节点作为桥梁，扫描其所有邻边，刷新其余外部节点到达集合 $S$ 的最短直连距离。
5. 循环迭代：重复步骤 2~4，直到所有 $n$ 个节点全部被吸纳进集合 $S$。

💡 高频易错点：Prim 与 Dijkstra 的本质异同

• Prim 维护的是节点到当前生成树集合的最短距离：dist[v] = min(dist[v], w);
• Dijkstra 维护的是节点到固定单源起点的累计路径长度：dist[v] = min(dist[v], dist[u] + w);

2. 算法选型对比

四、核心模型

1. 最小瓶颈生成树

• 定义：在一棵生成树中，最大边的权值称为该树的“瓶颈”。使得最大边权最小的生成树即为最小瓶颈生成树。
• 核心定理：任意最小生成树都必然是最小瓶颈生成树。
• 推导逻辑：Kruskal 算法严格按边权从小到大加边。为了使全图连通，最后加入的那条关键边，其权值正是为了达成连通性所不得不跨越的“最高门槛”。在所有合法的连通方案中，没有任何方案能够避开这一门槛，因此 MST 的最大边权在数学上已达到了所有生成树最大边权的理论下界。
• 应用推论：若边权是危险程度，要求“最大危险程度最小”，就求最小生成树的最大边权。若边权是承重，要求“最差道路承重最大”，方向正好相反：要按边权降序做 Kruskal，求最大生成树的最小边权。先看权值是越小越好还是越大越好，别被同一个“瓶颈”名字绕进去。

2. $k$ 个连通块问题

• 场景：需要将图划分为 $k$ 个独立部落、区域或无线电基站簇，求连通块间的最大间距或最小建设成本。
• 推导逻辑：
  • 初始状态下全图共有 $n$ 个互不连通的单点（连通块数为 $n$）。
  • 在 Kruskal 算法中，每成功合并一条合法树边，连通块总数就精确减少 1。
  • 合并 $n - 1$ 条边时，全图聚合成 1 个连通块（整棵生成树）。
• 状态控制：若需要最终保留 $k$ 个连通块，只需在成功合并 $n - k$ 条边时立刻终止算法！此时：
  • 前 $n - k$ 条边在各连通块内部构建了最优骨干；
  • 下一条即将合并不同连通块的候选边，其权值正是不同集合之间的“最近跨界距离”。

3. 虚拟超级源点

• 场景：铺设电网或供水系统时，节点既可以通过管道相互连通共享资源（边权代价 $w$），也可以在本地自建发电站/水库（点权代价 $c_i$）。
• 核心痛点：点权（自建）与边权（连线）属于两套不同维度的代价，常规生成树算法无法直接处理点权。
• 转化技巧：建立一个编号为 $0$ 的“虚拟超级源点”（代表国家主电网/天然水源）。
  • 对于每个具有自建成本的点 $i$，建立一条从 $0$ 到 $i$、权值为 $c_i$ 的虚拟边。
• 物理映射：“节点 $i$ 决定本地自建”完全等价于“节点 $i$ 与超级源点 $0$ 连通一条边”。
• 统一求解：在这张包含 $n + 1$ 个顶点的拓展图上直接跑一次标准 Kruskal，算法会在“自建虚拟边”与“城市互联边”之间自动完成全局贪心权衡。
• 代码提醒：并查集初始化要包括 0，现在共有 $n+1$ 个点，选满的是 $n$ 条边，不再是 n-1。

4. 已有连接与“零代价”预处理

• 场景：图中某些道路已经修好，或题目硬性规定某些边必须存在于最终的生成树中。
• 推导逻辑：已经建好的连接不再计入新增成本；真正的必选边若需要付费，求最终总造价时要先加上它们的费用。
• 实现要点：无需修改 Kruskal 核心。在全局普通候选边排序之前，先遍历这些“必选边”，用并查集提前合并端点，只有 find(u) != find(v)、确实合并了两个连通块时才让 cnt++。已建道路里有环没关系；但若题目要求这些边全都选进最终生成树，必选边自己成环就直接无解。之后将剩余的候选边正常排序、跑 Kruskal 即可。如果候选边与必选边产生环，会在 find(u) == find(v) 时被自动过滤，完美融合。

5. 边权相等与 MST 唯一性判定

• 场景：题目询问最小生成树的形态是否唯一。
• 推导逻辑：Kruskal 对权值完全相同的边，其相对排序位置是随机的。如果某条候选边在考察时，发现它的两个端点已经被其他同权边捷足先登地连通了，就说明发生了“同权平替”。只要能发生同权平替，生成树的最终拓扑形态就一定不唯一（虽然总代价依然绝对唯一）。

落到代码：同权边一组一组处理。 主并查集只维护权值严格小于当前 $w$ 的边形成的连通块。

1. 先用主并查集求本组每条边两端的根 fu,fv；若相同，直接忽略，这条边不是同权平替候选。
2. 把剩下的根当作临时图节点，用一份临时并查集逐条合并。本组中若有一次合并发现两端已连通，就形成了同权环（两条平行边也算），MST 不唯一。
3. 本组检查结束后，再把本组边合并进主并查集；临时并查集只重置本组用过的根，别每组清空全部 $n$ 个点。
4. 最后仍须检查原图是否连通；不连通时没有 MST，不能判成“唯一”。

另一种路径最大边判法见《最小生成树 (MST)：Kruskal 算法与 Prim 简介》第十节。

6. 不连通图与最小生成森林

• 场景：全图天生被划分为几个互不相连的岛屿，物理上根本无法形成一棵全局连通的大树。
• 推导逻辑：Kruskal 是一种纯粹的贪心算法，只要按权值升序遍历，它就会在每个互不相通的连通块内部，各自默默生长出最优骨干。
• 实现要点：当遍历完所有 $m$ 条边后，若 cnt < n - 1，说明原图不连通。此时 ans 累加的就是各独立连通块 MST 的权值之和，构成的整体就是最小生成森林。此时不需要死板地抛出无解（如 orz），要根据题意灵活返回这个森林总权值。

五、时光倒流：动态删边与逆向并查集（选学）

先修要求：熟练掌握并查集的基础原理与离线处理思想；可先看《并查集的演进》第四节。本节只维护连通性，不是在动态维护 MST 权值。

1. 暴力删边的痛点与逆向破局

场景：给定一张连通图，系统会依次“摧毁”给定的几条边。要求回答每次摧毁后，图当前的连通块数量或连通性。 物理劣势：并查集天生支持“合并”（加边），但完全不支持“分裂”（删边）。如果顺着题意，每次删边后都清空全图重跑一次 Kruskal 计数，遇到 $10^5$ 级别的极端数据，复杂度 $O(q \cdot m \log m)$ 必然导致 TLE。 降维打击（时光倒流）：我们先把所有的破坏操作统统存下来（离线查询），直接跳到时间线的尽头！

1. 终局建图：在初始图上，把那些“自始至终都没被炸毁”的幸存边挑出来，先用它们建好最终状态的并查集骨架。
2. 倒推重建：从最后一次破坏操作开始，逆序往前推。刚才被“摧毁”的边，在时间倒流的视角下，等价于被“重新铺设”！ 这样一来，棘手且昂贵的“删边分裂”操作，瞬间变回了我们最得心应手的“加边合并”操作。

2. 动态连通块计数实战演示

这里提供一份极简的实战代码，演示如何通过“时光倒流”来动态维护删边后的连通块数量。约定每条边最多删除一次，操作中给出的都是合法边编号。

关键状态跟踪：

• 初始视所有 $n$ 个点为孤立的 $n$ 个连通块。
• 每成功执行一次有效合并（即端点属于不同集合），全图连通块总数就减 1。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 100005;
const int M = 200005;

struct Edge { int u, v; } e[M];
int fa[N], del[M], ans[M];
int op[M]; // 记录每次摧毁的边序号

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void solve() {
    int n, m, q;
    // 独立输入范围：n, m, q <= 100000。点编号 1 到 n。
    if (!(cin >> n >> m >> q)) return;

    for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v;

    // 1. 离线读入所有摧毁操作，并打上封条
    for (int i = 1; i <= q; i++) {
        cin >> op[i];
        del[op[i]] = 1; 
    }

    // 初始化孤立并查集
    for (int i = 1; i <= n; i++) fa[i] = i;
    int blocks = n; // 初始为 n 个散点连通块

    // 2. 终局建图：加入所有未被摧毁的幸存边
    for (int i = 1; i <= m; i++) {
        if (!del[i]) {
            int fu = find(e[i].u), fv = find(e[i].v);
            if (fu != fv) { fa[fu] = fv; blocks--; }
        }
    }

    // 3. 时光倒流：逆序处理删边操作，化删为建
    for (int i = q; i >= 1; i--) {
        ans[i] = blocks; // 记录刚刚删边后（即建边前）的连通块数量
        int edge_idx = op[i];
        int fu = find(e[edge_idx].u), fv = find(e[edge_idx].v);
        
        // 把这条边加回来（时间倒流等于修复）
        if (fu != fv) { fa[fu] = fv; blocks--; }
    }

    // 4. 正序输出结果
    for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}

/* 
样例输入：
4 4 3
1 2
2 3
3 4
4 1
1
2
3

样例输出：
1
2
3

说明：初始全连通。
删边1(1-2)后，仍通过3-4-1连通(块数1)。
删边2(2-3)后，点2独立(块数2)。
删边3(3-4)后，点3独立(块数3)。
*/

六、练习题单

1. 第一阶梯：算法模板与连通性验证

1. 洛谷 P3366 【模板】最小生成树（已练可跳）

   • 核心考点：Kruskal 边排序与并查集路径压缩，处理图不连通的边界输出。
   • 训练指引：熟练在 3 分钟内默写出带路径压缩和 cnt == n - 1 剪枝的 Kruskal 标准模板。

2. 洛谷 P2820 局域网

   • 核心考点：最小生成森林的补集权值。
   • 训练指引：要求拆除尽可能多的线路权值，同时保持原来能互通的节点仍然互通。原图不一定全连通，分别给每个连通块留下一棵最小生成树即可，合起来就是最小生成森林。先累加所有边权 $Sum_{all}$，再用 Kruskal 累加保留的边权 $Sum_{forest}$，答案为 $Sum_{all} - Sum_{forest}$。这里不要求选满 $n-1$ 条边，也不要照搬上一题的 orz 判定。

2. 第二阶梯：模型转化与贪心剪枝

3. 洛谷 P2330 [SCOI2005] 繁忙的都市

   • 核心考点：最小瓶颈生成树。
   • 训练指引：要求选出 $n - 1$ 条道路且最大道路分值最小。直接套用 Kruskal 算法，最后加入生成树的那条边的权值即为答案。

4. 洛谷 P1195 口袋的天空（已练可跳）

   • 核心考点：$k$ 个连通块合并终止条件。
   • 训练指引：把棉花糖组合成 $k$ 个连通块。直接修改 Kruskal 的终止判定，将计数器达到 $n - k$ 作为完成标志，若边遍历完仍未达标则无解。

5. 洛谷 P1194 买礼物（已练可跳）

   • 核心考点：虚拟超级源点构建。
   • 训练指引：每个物品原价为 $A$（本地点权成本），若拥有某物品可以优惠价购买另一物品（边权成本）。建立 $0$ 号虚拟节点向每个物品连接权值为 $A$ 的边，全图跑 MST 求解。
   • 读题提醒：优惠矩阵中的 0 表示没有优惠，不能当作一条免费边。

3. 专题练习：统一建模与逆向维护

6. 【自拟练习】修路工程预处理

   • 核心考点：已有连接与必选边的提前合并。
   • 训练指引：给定 $N$ 个村庄，其中 $K$ 条道路已建成。要求继续建路使全图连通且新建成本最小。在排序普通可建道路前，先用并查集合并 $K$ 条已建道路的端点，不增加总成本。之后对剩余可建边跑标准 Kruskal。

7. 【自拟练习】最小生成树唯一性判定

   • 核心考点：同权平替判定。
   • 训练指引：按第四节第 5 小节的同权分组流程实现。不要只看 find(u)==find(v)，必须区分“更小权值早已连通”和“本组同权边形成环”。

8. 【自拟练习】脆弱的生命线（并查集删边）

   • 核心考点：时光倒流，逆向处理连通性。
   • 训练指引：也就是第五节演示代码的完整实战。理解为什么必须离线读取操作，以及如何通过逆向扫描把“破坏”优雅地转变为“建设”。