GESP 题解库 / 8 级题解 / [GESP202509 八级] 最小生成树 · 第 5 / 24 题
GESP202509 八级 · P14080 · 困难

删掉一条边后的最小生成树

先跑一次 Kruskal 定下 MST:非树边删了不影响;树边删了要用"跨过这个割的最小非树边"顶替。

🌲
n, m ≤ 10⁵
结点数与边数
✂️
m 个答案
每条边都要回答
⚡
O(m log m + m α(n))
Kruskal + 跳跃并查集
🎯
非树边 = S,树边 = S − w + 替换
核心结论
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定一张包含 n 个结点 m 条边的带权连通无向图。对于每条边,求出从图中移除该条边后,图的最小生成树中所有边的权值之和。特别地,若移除某条边后最小生成树不存在,则输出 -1。

输出共 m 行,第 i 行对应"删掉输入中第 i 条边"的答案。

样例输入输出
样例 15 5
1 2 4
2 3 3
3 4 1
2 5 2
3 1 8
14
15
-1
-1
10
样例 26 10
1 2 6
2 3 3
3 1 4
3 4 5
4 5 8
5 6 2
6 4 1
3 2 4
5 4 4
3 3 6
15
16
17
-1
15
17
18
15
15
15
💡
人话翻译:一条一条边地试——把第 i 条边扣掉,剩下的图明显更"瘦"了,再问一遍"你的最小生成树多重"。
如果每条边都删掉重跑一次 Kruskal,是 O(m² log m),m = 10⁵ 必然超时。
突破口:先只看一次 MST。记这次的总和为 S,并区分两类边:
① 不在 MST 里的边:删掉它,原来那棵 MST 一根手指头都没动,所以答案就是 S;
② 在 MST 里的边 e:删掉 e 会把树裂成两块,必须找一条跨越这两块的最小非树边来顶替,答案 = S − w(e) + 替换边权;若没有任何边能跨越(说明 e 是桥),输出 -1。

🔍 关键词提取

最小生成树敏感性分析非树边替换割 / 桥按权升序覆盖路径并查集跳跃

已知条件

项目说明
输入第一行 n、m;随后 m 行每行 uᵢ、vᵢ、wᵢ
输出m 行,第 i 行是删掉第 i 条边后的 MST 边权和(不存在则 −1)
数据范围1 ≤ n ≤ 10⁵,1 ≤ m ≤ 10⁵
边权1 ≤ wᵢ ≤ 10⁹
起点连通原图连通,但删掉一条边后可能不再连通
可能的杂物平行边、自环都可能出现
部分分20% 时 n ≤ 50、m ≤ 100;另有 30% 满足 n = m

需要解决的问题

02
思维导图
整理解题思路的全貌
🌲 一次 Kruskal 定全局,再把边分两类
① 第一遍 Kruskal
边按 w 升序排序
能连通就选,得到一棵 MST
记总和 S,标记 inMST[i]
同时得到树的父子结构
② 非树边:直接给答案
删掉它 MST 一根边都没少
子图 MST 不可能更小
所以答案 = S
O(1) 搞定,占大多数边
③ 树边:找最小替换边
删掉后树裂成 A、B 两块
要一条跨割的边来补
非树边按权升序扫,占路径上未标记的树边
答案 = S − w(e) + 替换权
④ 并查集跳跃
jump(x) = 最近还没被占的祖先
被占的树边并入父结点
每条树边只被覆盖一次
总复杂度 O((n + m) α(n))
⚠️ 易错点
把"删掉后不连通"漏判成 S
替换边取成了同一条边
自环/平行边的处理
并查集跳跃忘记路径压缩
int 溢出
03
样例手算推导
样例 1 完整手推(含 −1 的两种情形)+ 样例 2 的桥

🧮 第 ① 步:跑一遍 Kruskal,拿到 MST 与总和 S

样例 1:n = 5, m = 5,边按权升序为 3–4 (1)、2–5 (2)、2–3 (3)、1–2 (4)、3–1 (8)。

顺序边权值并查集动作是否进 MST
13–413、4 连成一块✅ 进
22–522、5 连成一块✅ 进
32–33两块合并成 {2,3,4,5}✅ 进
41–24{2,3,4,5} 并入 1 → 6 个点全通✅ 进
53–18两端早已连通❌ 不进(非树边)

S = 1 + 2 + 3 + 4 = 10,MST = { 3–4, 2–5, 2–3, 1–2 }

1
把 MST 画成树(以 1 为根)

1 的孩子是 2;2 的孩子是 3 和 5;3 的孩子是 4

于是每条非树边都能对应到树上一条唯一的路径

例:非树边 3–1 对应路径 3 → 2 → 1,会覆盖树边 2–3 与 1–2

树结构建立完成

🧮 第 ② 步:逐条边给出答案

1
第 1 条边 1–2(w = 4,树边)

删掉它,树裂成 {1} 与 {2,3,4,5}

跨割的边只有 3–1(w = 8),它就是最小替换边

答案 = 10 − 4 + 8 = 14 ✓

14

2
第 2 条边 2–3(w = 3,树边)

删掉它,树裂成 {1,2,5} 与 {3,4}

跨割的边同样只有 3–1(w = 8)

答案 = 10 − 3 + 8 = 15 ✓

15

3
第 3 条边 3–4(w = 1,树边)

删掉它,树裂成 {4} 与 {1,2,3,5}

跨割的边:一条也没有(3–4 是桥)

图不连通 → 输出 −1 ✓

−1

4
第 4 条边 2–5(w = 2,树边)

删掉它,树裂成 {5} 与 {1,2,3,4}

跨割的边:没有(2–5 也是桥)

输出 −1 ✓

−1

5
第 5 条边 3–1(w = 8,非树边)

它不在 MST 里,删掉之后 MST 原封不动

答案就是 S = 10 ✓

10

边(按输入顺序)类型割的两侧最小替换边答案
1–2 (4)树边{1} | {2,3,4,5}3–1(8)10 − 4 + 8 = 14
2–3 (3)树边{1,2,5} | {3,4}3–1(8)10 − 3 + 8 = 15
3–4 (1)树边{4} | 其余无(桥)−1
2–5 (2)树边{5} | 其余无(桥)−1
3–1 (8)非树边————S = 10
🔑
为什么"跨割的最小非树边"就是答案?
删掉树边 e 后,任何生成树都必须有一条边横跨 A–B;把 e 放回去、把其中权最小的那条换掉,就得到了一棵新生成树,权值是 S − w(e) + w(f)。
反过来,任何新生成树减掉一条跨割边就能还原成一棵原图的生成树,所以新 MST 不可能比它更小。
"按权升序扫非树边"正好让每条树边第一次被覆盖时拿到最小的替换权。

🧮 样例 2:桥与可替换树边的混合

样例 2 的 10 条边:1–2 (6)、2–3 (3)、3–1 (4)、3–4 (5)、4–5 (8)、5–6 (2)、6–4 (1)、3–2 (4)、5–4 (4)、3–3 (6)。

边类型替换边答案说明
1–2 (6)非树边——15删了不动 MST
2–3 (3)树边3–2(4)1615 − 3 + 4
3–1 (4)树边1–2(6)1715 − 4 + 6
3–4 (5)树边无(桥)−1左右两个三角只靠这条边相连
4–5 (8)非树边——15删了不动 MST
5–6 (2)树边5–4(4)1715 − 2 + 4
6–4 (1)树边5–4(4)1815 − 1 + 4
3–2 (4)非树边——15平行边:MST 已用 2–3
5–4 (4)非树边——15平行边:MST 已用 4–5
3–3 (6)自环——15自环永远不进 MST

S = 1 + 2 + 3 + 4 + 5 = 15,输出 15 16 17 −1 15 17 18 15 15 15 ✓

⚠️
两个特别容易写错的地方:① 3–4 是连接左右两个三角形的唯一通道,它是桥,删掉必然 -1——如果实现里只盯着"MST 的连通性"而不检查"跨割边是否存在",这里会错答成 15;
② 自环 3–3 与平行边 3–2 / 5–4 都不该影响 MST 结果:自环连自己,平行边只需要留权值最小的那条。Kruskal 天然解决这两件事,但如果你手工预处理边集,一定不要把平行边合并掉——删掉一条平行边时,另一条就是它的替换边。
04
解法对比
Kruskal + 非树边升序覆盖 vs 每条边删掉重跑 Kruskal

⚔️ 解法对比

🟢 Kruskal + 非树边升序覆盖(推荐) 推荐

一次 Kruskal 定 MST;非树边直接给 S;树边用"按权升序的非树边 + 并查集跳跃"标记最小替换边

  • 时间 O(m log m + m α(n))
  • 每条树边只被覆盖一次
  • 代码约 90 行
  • n = m = 10⁵ 秒过
💡
正确性来源:删除树边 e 后,新 MST 一定形如 "MST − e + f"(f 为跨割边上权值最小者);而按权升序扫描时,第一条覆盖到 e 的非树边恰好就是那个 f。
并查集跳跃让"已经被覆盖的树边"整体跳过,保证总扫描量是 O(m α(n))。

🟠 每条边删掉重跑 Kruskal

对 i = 1 … m,把第 i 条边扣掉再跑一次 Kruskal

  • 时间 O(m² log m)
  • 代码极短(20 行)
  • m = 10⁵ 时约 10¹⁰
  • 只能拿 n、m ≤ 500 的部分分
⚠️
它的价值:正是本题最好的对拍工具——小数据下手写它,随机构造几百组图和大数据答案比一比,
能瞬间发现"桥没判""替换边取错"这类隐蔽 bug。

📈 性能对比

方案复杂度代码量
Kruskal + 升序覆盖O(m log m + m α(n))✅ 正解,约 90 行
逐边删掉重跑 KruskalO(m² log m)⭕ 只够小数据,约 25 行
逐边删掉跑 PrimO(n m log n)❌ 更慢,约 40 行
05
算法流程图
一次 Kruskal 定框架,非树边升序覆盖树边
开始读入 n、m 与 m 条边 (u, v, w)把所有边按权值升序排序,跑第一遍 KruskalS = MST 的边权和,并标记每条边是否属于 MST以 1 为根建出 MST 的树结构(父结点、深度、连向父结点的边号)按权值升序枚举每一条非树边 (u, v, w)u、v 的"最近未覆盖祖先"还是两个不同的点吗?是 ✓还要往上爬否 ✗这条非树边扫完把较深的一侧往上跳一格,把那条树边的替换权记成 w被覆盖过的树边并入父结点(并查集跳跃),下次直接跳过按输入顺序输出:非树边给 S,树边给 S − w + 替换权,没人替则 −1两端还没汇合,继续往上爬
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🌲 逐边删除后的 MST 权值和

第 1 行输入 n m,随后 m 行每行 u v w。程序会先算出原图的 MST 与总和 S,再逐条边扣掉重新计算,把"是否树边、替换边、答案"一次列清。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(Kruskal + 非树边升序 + 并查集跳跃)

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

typedef long long ll;
const int MAXN = 100005;

int n, m;
int U[MAXN], V[MAXN];
ll  W[MAXN];
int ord[MAXN];                    // 按边权升序排好的边号
bool inMST[MAXN];

int p[MAXN];                      // Kruskal 用的并查集
int up[MAXN];                     // "跳跃"并查集:指向最近的未被覆盖祖先
int par[MAXN], dep[MAXN], pe[MAXN];        // 父、深度、连向父结点的边号
vector< pair<int, int> > tree[MAXN];       // MST 的邻接表:(邻居, 边号)
ll  repl[MAXN];
bool hasRepl[MAXN];
ll  S = 0;

int fd(int x)   { while (p[x]  != x)  { p[x]  = p[p[x]];   x = p[x];   } return x; }
int jump(int x) { while (up[x] != x)  { up[x] = up[up[x]]; x = up[x];  } return x; }

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) scanf("%d %d %lld", &U[i], &V[i], &W[i]);

    for (int i = 1; i <= m; i++) ord[i] = i;
    sort(ord + 1, ord + m + 1, [](int x, int y) { return W[x] < W[y]; });

    // ---------- ① 第一遍 Kruskal ----------
    for (int i = 1; i <= n; i++) p[i] = i;
    for (int k = 1; k <= m; k++) {
        int i = ord[k], u = U[i], v = V[i];
        if (u == v) continue;                 // 自环永远不进 MST
        int ru = fd(u), rv = fd(v);
        if (ru != rv) { p[ru] = rv; inMST[i] = true; S += W[i]; }
    }

    // ---------- ② 建 MST 的树结构 ----------
    for (int i = 1; i <= m; i++) if (inMST[i]) {
        tree[U[i]].push_back(make_pair(V[i], i));
        tree[V[i]].push_back(make_pair(U[i], i));
    }
    for (int i = 1; i <= n; i++) { par[i] = 0; dep[i] = -1; pe[i] = 0; up[i] = i; }
    dep[1] = 0;
    stack<int> st; st.push(1);
    while (!st.empty()) {
        int x = st.top(); st.pop();
        for (int t = 0; t < (int)tree[x].size(); t++) {
            int y = tree[x][t].first, ei = tree[x][t].second;
            if (dep[y] == -1) { dep[y] = dep[x] + 1; par[y] = x; pe[y] = ei; st.push(y); }
        }
    }

    // ---------- ③ 非树边按权升序,覆盖路径上的树边 ----------
    for (int k = 1; k <= m; k++) {
        int i = ord[k], u = U[i], v = V[i];
        if (inMST[i] || u == v) continue;      // 树边 / 自环都不用处理
        while (jump(u) != jump(v)) {
            if (dep[jump(u)] < dep[jump(v)]) swap(u, v);   // 总是爬较深的一侧
            int x = jump(u);
            if (!hasRepl[pe[x]]) { hasRepl[pe[x]] = true; repl[pe[x]] = W[i]; }
            up[x] = jump(par[x]);              // 并入父结点,下次跳过
            u = par[x];
        }
    }

    // ---------- ④ 输出答案 ----------
    for (int i = 1; i <= m; i++) {
        if (!inMST[i])                 printf("%lld\n", S);                    // 非树边
        else if (!hasRepl[i])          printf("-1\n");                         // 桥
        else                           printf("%lld\n", S - W[i] + repl[i]);   // 替换
    }
    return 0;
}
🔑
四个要点:① 第一遍 Kruskal 一定要边排序后记录边号,后面还要按输入顺序输出答案;② 树结构必须以某个根(这里取 1)建好父子关系,否则"往上爬"没有方向;③ 覆盖时只记第一次(if (!hasRepl[pe[x]])),因为非树边是升序扫的,第一次覆盖就是最小替换边;④ jump(x) 是"最近还没被覆盖的祖先",被覆盖的树边要 up[x] = jump(par[x]) 并进去。

📖 关键几行怎么看

代码作用为什么这样写
if (u == v) continue;跳过自环自环的两个端点相同,永远不可能连接两个不同连通块
if (ru != rv) { ... inMST[i] = true; }标记树边Kruskal 选中的边就是 MST 的边,其余都是非树边
if (dep[jump(u)] < dep[jump(v)]) swap(u, v);爬深的一侧保证每次都在向 LCA 靠近,循环必然终止
up[x] = jump(par[x]);并查集跳跃被覆盖的树边整体并进父结点,重复扫描直接跳过
S - W[i] + repl[i]树边答案把 e 换成跨割最小非树边,重连成新生成树
printf("-1 ")桥没有任何非树边跨过这条割,删掉后图不连通
⚠️
五个坑:① 忘了 n = 1 的特例:此时 MST 权为 0,每条边(都是自环)答案都是 0;② 把桥误判成 S:树边如果从没被非树边覆盖过,必须输出 -1;③ 用"非树边的最小值"替代"跨割最小非树边"——两者完全不同,必须靠路径覆盖确定跨越关系;④ 忘记路径压缩,跳跃并查集退化成 O(链长);⑤ 用 int 存 S(10¹⁴ 溢出)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
5 5
1 2 4
2 3 3
3 4 1
2 5 2
3 1 8
14
15
-1
-1
10
题面样例 1(两条桥 + 一条非树边)
6 10
1 2 6
2 3 3
3 1 4
3 4 5
4 5 8
5 6 2
6 4 1
3 2 4
5 4 4
3 3 6
15
16
17
-1
15
17
18
15
15
15
题面样例 2(S = 15,含自环与两组平行边)
1 1
1 1 5
0n = 1:MST 权为 0,自环删掉答案仍是 0
2 1
1 2 9
-1唯一的边就是桥,删掉后不连通
2 2
1 2 5
1 2 5
5
5
平行边:删掉任意一条,另一条顶上
3 3
1 2 1
2 3 1
1 3 100
101
101
2
两条便宜边是桥,必须借来 100 那条;非树边保持 S = 2
4 3
1 2 1
2 3 2
3 4 3
-1
-1
-1
整条链:每条边都是桥
✅
自查清单:① 第一遍 Kruskal 标记了树边吗?② 非树边是不是直接输出 S?③ 树边找到跨割的最小非树边了吗(没找到 → -1)?④ n = 1 特判了吗?⑤ 全程 long long 吗?

🚨 易错点清单

⚠️
把桥答成 S:树边若没有任何非树边跨过它,删掉后图不连通,必须输出 -1。
⚠️
误用"全局最小非树边"当替换边:替换边必须跨过这条树边对应的割,只有覆盖了该树边的非树边才合格。
⚠️
没处理 n = 1:此时并没有"树边",所有边(自环)的答案都是 0,别输出 -1。
⚠️
平行边被合并:平行边可能是彼此的替换边,合并成一条会漏解。
⚠️
int 溢出:S 可达 10⁵ × 10⁹ = 10¹⁴,必须 long long。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(m log m + m α(n))
空间复杂度
O(n + m)
排序
只需 1 次
跳跃并查集
每条树边最多被覆盖 1 次

时间怎么算的?

空间都用在哪?

6 个长度 m 的数组(U、V、W、ord、inMST、repl)与 6 个长度 n 的数组(p、up、par、dep、pe、hasRepl),加上 MST 邻接表 2(n − 1) 条边。

✅ 这就是本题正解的复杂度:把 m 次"重跑 Kruskal"压缩成一次排序 + 一次路径覆盖。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 「最小生成树 + 逐边删除」通用模板
// ① 跑一次 Kruskal:S = 边权和,inMST[i] 标记每条边
// ② 以某个点为根建树:par / dep / 连向父结点的边号 pe
// ③ 非树边按权升序排序
// ④ 对每条非树边 (u, v, w):
//        while (jump(u) != jump(v)) {
//            if (dep[jump(u)] < dep[jump(v)]) swap(u, v);
//            x = jump(u);
//            if (!hasRepl[pe[x]]) { hasRepl[pe[x]] = 1; repl[pe[x]] = w; }
//            up[x] = jump(par[x]);     // 这条树边永久"退休"
//            u = par[x];
//        }
// ⑤ 回答:非树边 -> S;树边且有替换 -> S - w + repl;树边无替换 -> -1

// 为什么"按权升序"就够
//   删除树边 e 后,新 MST = MST - e + f,f 是跨 e 两侧割的最小非树边
//   升序扫描保证第一条"覆盖到 e"的非树边恰好是那个最小的 f

// 为什么"并查集跳跃"是 O(总边数)
//   每条树边只会被覆盖一次,覆盖后立刻并入父结点
//   于是 while 循环里的总跳数 <= n,外加路径压缩

// 别忘了 n == 1:MST 权为 0,所有边(自环)答案都是 0
// 以及 long long:S 最大 1e5 * 1e9 = 1e14

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
树边 / 非树边分类一次 Kruskal 就分出两类,答案公式完全不同MST 相关的所有"最短路/唯一性"类问题
替换边思想删边后必须用"跨割最小边"顶替MST 唯一性判定、次小生成树、MST 计数
按权升序覆盖路径非树边升序扫,第一次覆盖即最优树上路径染色、离线维护"每条树边的最小跨越边"
并查集跳跃 / 缩点被处理的树边并入父结点,永久跳过Kruskal 重构树思路、树上路径的离线缩点
桥与连通性判定没有被任何非树边跨越的树边就是桥割边 / 割点、双连通分量预处理
🌟
思考题:如果题目改成"删掉任意两条边",或者问"有多少条边删掉后 MST 权值变大",上面的算法还能改造吗?(提示:① 问"变大"只需看是否存在跨割非树边——hasRepl[i] 为真时 repl[i] > w(e) 才会变大(相等则不变量);② 删两条边会同时影响两个割,需要用 次小替换边(同一割上的第二小非树边),也就是把"路径覆盖取第一条"改成"每条树边保留前 2 小"。这类"把一次覆盖升级成 k 次覆盖"的思路,是 MST 敏感性分析题的标准进阶。)