先跑一次 Kruskal 定下 MST:非树边删了不影响;树边删了要用"跨过这个割的最小非树边"顶替。
给定一张包含 n 个结点 m 条边的带权连通无向图。对于每条边,求出从图中移除该条边后,图的最小生成树中所有边的权值之和。特别地,若移除某条边后最小生成树不存在,则输出 -1。
输出共 m 行,第 i 行对应"删掉输入中第 i 条边"的答案。
| 样例 | 输入 | 输出 |
|---|---|---|
| 样例 1 | 5 5 | 14 |
| 样例 2 | 6 10 | 15 |
i 条边扣掉,剩下的图明显更"瘦"了,再问一遍"你的最小生成树多重"。O(m² log m),m = 10⁵ 必然超时。S,并区分两类边: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 |
n − 1 条边就能连通全图,删掉一条没被用到的边,这棵生成树依然存在且权值不变;而子图的最小生成树不可能比原来的更小,所以答案恰好还是 Se 把树分成两块 A、B,新生成树必须有一条边横跨 A–B。取跨越这个割的权值最小的非树边 f,则 MST − e + f 就是新图的最小生成树,答案 = S − w(e) + w(f)10⁵ × 10⁹ = 10¹⁴,int 装不下样例 1:n = 5, m = 5,边按权升序为 3–4 (1)、2–5 (2)、2–3 (3)、1–2 (4)、3–1 (8)。
| 顺序 | 边 | 权值 | 并查集动作 | 是否进 MST |
|---|---|---|---|---|
| 1 | 3–4 | 1 | 3、4 连成一块 | ✅ 进 |
| 2 | 2–5 | 2 | 2、5 连成一块 | ✅ 进 |
| 3 | 2–3 | 3 | 两块合并成 {2,3,4,5} | ✅ 进 |
| 4 | 1–2 | 4 | {2,3,4,5} 并入 1 → 6 个点全通 | ✅ 进 |
| 5 | 3–1 | 8 | 两端早已连通 | ❌ 不进(非树边) |
S = 1 + 2 + 3 + 4 = 10,MST = { 3–4, 2–5, 2–3, 1–2 }
1 的孩子是 2;2 的孩子是 3 和 5;3 的孩子是 4
于是每条非树边都能对应到树上一条唯一的路径
例:非树边 3–1 对应路径 3 → 2 → 1,会覆盖树边 2–3 与 1–2
树结构建立完成
删掉它,树裂成 {1} 与 {2,3,4,5}
跨割的边只有 3–1(w = 8),它就是最小替换边
答案 = 10 − 4 + 8 = 14 ✓
14
删掉它,树裂成 {1,2,5} 与 {3,4}
跨割的边同样只有 3–1(w = 8)
答案 = 10 − 3 + 8 = 15 ✓
15
删掉它,树裂成 {4} 与 {1,2,3,5}
跨割的边:一条也没有(3–4 是桥)
图不连通 → 输出 −1 ✓
−1
删掉它,树裂成 {5} 与 {1,2,3,4}
跨割的边:没有(2–5 也是桥)
输出 −1 ✓
−1
它不在 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)。样例 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) | 16 | 15 − 3 + 4 |
| 3–1 (4) | 树边 | 1–2(6) | 17 | 15 − 4 + 6 |
| 3–4 (5) | 树边 | 无(桥) | −1 | 左右两个三角只靠这条边相连 |
| 4–5 (8) | 非树边 | —— | 15 | 删了不动 MST |
| 5–6 (2) | 树边 | 5–4(4) | 17 | 15 − 2 + 4 |
| 6–4 (1) | 树边 | 5–4(4) | 18 | 15 − 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 天然解决这两件事,但如果你手工预处理边集,一定不要把平行边合并掉——删掉一条平行边时,另一条就是它的替换边。一次 Kruskal 定 MST;非树边直接给 S;树边用"按权升序的非树边 + 并查集跳跃"标记最小替换边
e 后,新 MST 一定形如 "MST − e + f"(f 为跨割边上权值最小者);而按权升序扫描时,第一条覆盖到 e 的非树边恰好就是那个 f。O(m α(n))。对 i = 1 … m,把第 i 条边扣掉再跑一次 Kruskal
| 方案 | 复杂度 | 代码量 |
|---|---|---|
| Kruskal + 升序覆盖 | O(m log m + m α(n)) | ✅ 正解,约 90 行 |
| 逐边删掉重跑 Kruskal | O(m² log m) | ⭕ 只够小数据,约 25 行 |
| 逐边删掉跑 Prim | O(n m log n) | ❌ 更慢,约 40 行 |
第 1 行输入 n m,随后 m 行每行 u v w。程序会先算出原图的 MST 与总和 S,再逐条边扣掉重新计算,把"是否树边、替换边、答案"一次列清。
点按钮开始 →
#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; }
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¹⁴ 溢出)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 5 | 14 15 -1 -1 10 | 题面样例 1(两条桥 + 一条非树边) |
6 10 | 15 16 17 -1 15 17 18 15 15 15 | 题面样例 2(S = 15,含自环与两组平行边) |
1 1 | 0 | n = 1:MST 权为 0,自环删掉答案仍是 0 |
2 1 | -1 | 唯一的边就是桥,删掉后不连通 |
2 2 | 5 5 | 平行边:删掉任意一条,另一条顶上 |
3 3 | 101 101 2 | 两条便宜边是桥,必须借来 100 那条;非树边保持 S = 2 |
4 3 | -1 -1 -1 | 整条链:每条边都是桥 |
S?③ 树边找到跨割的最小非树边了吗(没找到 → -1)?④ n = 1 特判了吗?⑤ 全程 long long 吗?-1。0,别输出 -1。S 可达 10⁵ × 10⁹ = 10¹⁴,必须 long long。O(m log m);第一遍 Kruskal 的并查集开销 O(m α(n))O(n + m)n,配合路径压缩为 O((n + m) α(n))2 × 10⁶ 次操作,1 秒时限轻松通过6 个长度 m 的数组(U、V、W、ord、inMST、repl)与 6 个长度 n 的数组(p、up、par、dep、pe、hasRepl),加上 MST 邻接表 2(n − 1) 条边。
✅ 这就是本题正解的复杂度:把 m 次"重跑 Kruskal"压缩成一次排序 + 一次路径覆盖。
// 「最小生成树 + 逐边删除」通用模板 // ① 跑一次 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 重构树思路、树上路径的离线缩点 |
| 桥与连通性判定 | 没有被任何非树边跨越的树边就是桥 | 割边 / 割点、双连通分量预处理 |
hasRepl[i] 为真时 repl[i] > w(e) 才会变大(相等则不变量);② 删两条边会同时影响两个割,需要用 次小替换边(同一割上的第二小非树边),也就是把"路径覆盖取第一条"改成"每条树边保留前 2 小"。这类"把一次覆盖升级成 k 次覆盖"的思路,是 MST 敏感性分析题的标准进阶。)