最小生成树 题解

题目分析

给定一张带权连通无向图，有 $n$ 个结点和 $m$ 条边。要求对于每一条边，求出删除这条边后，图中最小生成树的边权和。如果删除后图不再连通，则输出 $-1$。

原图的最小生成树记为 MST。对于某条边 $e$，有两种情况：

1. $e$ 不在 MST 中
   删除它不会影响 MST 的连通性和最小性，答案就是原 MST 的边权和 $S$。

2. $e$ 在 MST 中
   删除 $e$ 后，MST 被分成两个连通块。我们需要找一条最小的非树边（不在原 MST 中的边），且它的两个端点恰好分别在这两个连通块中，用这条非树边重新连接两棵子树。
   更形象地说，在 MST 中每条非树边会和树上的路径形成一个环，删除这个环上的任意一条树边后，都可以用该非树边替换它。
   因此，对于 MST 中的边 $e$，答案等于 原 MST 权值和 $S$ 减去 $e$ 的权值，再加上能替换它的最小非树边的权值。若不存在能替换的非树边（即删去后图不连通），则答案为 $-1$。

问题转化为：对于 MST 上的每条树边，求出能替换它的最小非树边权值（称为“替换代价”）。最后对于每条边输出对应答案。

解题思路

1. 构建原 MST

使用 Kruskal 算法或 Prim 算法求出原图的最小生成树，记录：

• MST 的边权和 $S$
• 哪些边在 MST 中（记为树边）
• 哪些边不在 MST 中（记为非树边）

2. 将 MST 建成一棵有根树

在 MST 上进行一次深度优先遍历（DFS），求出每个点的深度 dep，以及每个点与父结点相连的那条树边的编号 pid。这样 MST 就变成了一棵以某个结点为根的有根树。

3. 处理所有非树边，更新树边的替换代价

对于每条非树边 $e(u,v,w)$，它可以在 MST 上连接 $u$ 到 $v$ 的路径形成一个环。这意味着这条路径上的任意一条树边，都可以用 $e$ 替换，替换后的总代价为 $S - w_{\text{树边}} + w$。

为了找到每一条树边的最小替换代价，我们需要对所有非树边执行类似的操作：将 $u$ 到 $v$ 路径上尚未确定最小替换代价的树边全部更新。直接暴力跳路径会超时，这里可以借助并查集进行路径压缩优化，使每条树边只被更新一次。

具体做法：

• 将非树边按边权从小到大排序（优先使用更优的替换边）。
• 初始化每个结点的并查集父结点为自己。
• 对于每条非树边 $(u,v,w)$：
  • 找到 $u$ 和 $v$ 在并查集中的根（代表沿树向上目前还未处理完的结点）。
  • 每次让深度较大的结点向上跳，将其与父结点之间的树边的答案更新为 $S - w_{\text{树边}} + w$，并把这个结点和它的父结点在并查集中合并（路径压缩），表示该树边已经被处理过。
  • 重复直到 $u$ 和 $v$ 相遇（到达它们的 LCA）。

这样每条树边只会被访问常数次，整体效率很高。

4. 输出答案

• 对于原 MST 中的边：如果它的替换代价未被更新（保持初始的无穷大），说明没有非树边能替换它，输出 $-1$；否则输出替换代价。
• 对于不在 MST 中的边：直接输出 $S$。

算法说明

算法主要分为以下几步：

1. 读入并存储边，用 p 数组记录边的原始编号。
2. Kruskal
   • 按边权升序排序边的编号。
   • 用并查集维护连通性，选出 $n-1$ 条树边，标记 mark[i]=1，累加 $S$，同时用邻接表存储 MST 的结构（无向图）。
3. DFS 建树
   从结点 $1$ 开始 DFS，记录每个结点深度和指向父结点的边编号。
4. 初始化答案数组
   树边初始答案设为无穷大（oo），非树边初始答案设为 $S$。
5. 非树边更新
   • 重新初始化并查集。
   • 按边权升序遍历所有非树边（排序后的 p 数组结合 mark 跳过树边）。
   • 对于非树边 $(u,v,w)$，利用深度和并查集逐步跳祖先，更新对应树边的答案，并进行路径压缩。
6. 输出
   小于 oo 则输出答案，否则输出 $-1$。

时间复杂度分析

• 排序边：$O(m \log m)$
• Kruskal：$O(m \alpha(n))$
• DFS：$O(n)$
• 非树边更新：每条树边只被更新一次，并查集操作几乎 $O(\alpha(n))$，故总体 $O(n \alpha(n) + m \log m)$ 或 $O((n+m)\alpha(n))$，足以在 $n,m \le 10^5$ 的范围内通过。

C++ 参考代码

以下是整理后的参考代码，对原代码中的细节做了补充和注释。

cpp
复制
1#include <cstdio>
2#include <algorithm>
3using namespace std;
4
5const int N = 1e5 + 5;
6const int M = 2e5 + 5;
7const long long oo = 1e18;          // 无穷大，表示无替换边
8
9int n, m;
10int u[M], v[M], w[M], p[M];        // 边的起、终、权、原始编号
11int h[N], id[M << 1], nx[M << 1], et;  // 邻接表（无向图需要双向边）
12int f[N], mark[M];                 // 并查集、标记是否为MST边
13long long s, ans[M];               // MST总权值、每条边答案
14int dep[N], pid[N];                // 深度，通往父结点的边编号
15
16// 边排序比较函数
17bool cmp(int x, int y) {
18    return w[x] < w[y];
19}
20
21// 并查集查找（路径压缩）
22int getf(int x) {
23    return f[x] ? f[x] = getf(f[x]) : x;
24}
25
26// 添加无向边到邻接表
27void link(int x, int edgeId) {
28    id[++et] = edgeId;
29    nx[et] = h[x];
30    h[x] = et;
31}
32
33// DFS 建树，记录深度和父边
34void dfs(int x, int fa = 0, int edgeId = 0) {
35    dep[x] = dep[fa] + 1;
36    pid[x] = edgeId;
37    for (int i = h[x]; i; i = nx[i]) {
38        int to = u[id[i]] ^ v[id[i]] ^ x; // 求邻边的另一端点
39        if (to != fa)
40            dfs(to, x, id[i]);
41    }
42}
43
44int main() {
45    scanf("%d%d", &n, &m);
46    for (int i = 1; i <= m; i++) {
47        scanf("%d%d%d", &u[i], &v[i], &w[i]);
48        p[i] = i;                     // 记录原始编号
49    }
50
51    // ---------- Kruskal 求 MST ----------
52    sort(p + 1, p + m + 1, cmp);
53    for (int i = 1; i <= m; i++) {
54        int x = u[p[i]], y = v[p[i]];
55        if (getf(x) == getf(y)) continue; // 已连通，跳过
56        mark[p[i]] = 1;                   // 标记为树边
57        f[getf(x)] = y;                   // 合并集合
58        s += w[p[i]];                     // 累加权值
59        link(x, p[i]);                    // 建无向边
60        link(y, p[i]);
61    }
62
63    // 初始化答案
64    for (int i = 1; i <= m; i++)
65        ans[i] = mark[i] ? oo : s;
66
67    // ---------- DFS 建立有根树 ----------
68    dfs(1);
69
70    // ---------- 重置并查集，用于非树边更新 ----------
71    for (int i = 1; i <= n; i++) f[i] = 0;
72
73    // ---------- 处理非树边 ----------
74    for (int i = 1; i <= m; i++) {
75        if (mark[p[i]]) continue;          // 只处理非树边
76        int x = getf(u[p[i]]), y = getf(v[p[i]]);
77        while (x != y) {
78            if (dep[x] < dep[y]) swap(x, y); // 保证 x 更深
79            int to = u[pid[x]] ^ v[pid[x]] ^ x; // x 的父结点
80            // 更新树边 pid[x]
81            ans[pid[x]] = s - w[pid[x]] + w[p[i]];
82            f[x] = to;                     // 路径压缩
83            x = getf(x);
84        }
85    }
86
87    // ---------- 输出 ----------
88    for (int i = 1; i <= m; i++)
89        printf("%lld\n", ans[i] < oo ? ans[i] : -1);
90
91    return 0;
92}

代码细节说明

• 邻接表建图：Kruskal 确定 MST 后，需要用 link 将 MST 存储为无向图，因此对每条树边调用了两次 link（两个方向）。DFS 时利用异或性质 u[id] ^ v[id] ^ x 快速得到当前边的另一端点，前提是读入的边存储方式支持这一运算。
• 并查集的两次使用：
  • 第一次在 Kruskal 中，用于判断连通性及合并；
  • 第二次在非树边更新中，用于记录树边上哪些结点已经处理过，实现路径压缩，确保每条树边只被更新一次。
• 答案的初始化：树边初始化为 oo，若最终仍为 oo 说明没有非树边能替换，输出 -1；非树边初始化为 S。
• 排序：非树边按权值升序处理，可以保证每条树边第一次被更新时就是最优（最小）替换代价，后续不再更新。

总结

本题的核心在于“替换边”思想的转化以及用并查集实现高效的树上路径更新。通过对 MST 建树 + 非树边排序 + 路径压缩，我们可以在 $O(m \log m)$ 的时间内求出每条边删除后新的最小生成树权值，完美应对 $n,m \le 10^5$ 的数据规模。这种技巧在生成树相关问题中非常经典，建议读者熟练掌握。