GESP 八级 · GESP 202603 C++ 八级 第 23 题

如果将一个连通无向图 $G_1$ 中所有边的权值都统一增加同一个正整数常数 $C$，形成图 $G_2$。则 $G_1$ 的最小生成树中每条边在 $G_2$ 中对应的边组成的树，一定是 $G_2$ 的最小生成树。（ ）

最小生成树：Prim（加点法，O(n²)或O(mlog n)）、Kruskal（加边法，O(mlog m)）。Kruskal需用并查集判环。

Kruskal算法需按边权排序，用并查集判断是否形成环。Prim算法适用于稠密图，Kruskal适用于稀疏图。

【考点】最小生成树｜Kruskal 算法逻辑｜贪心策略

考纲定位：本题考查《GESP 八级考纲》图论·最小生成树·性质推断模块。命题人卡住的是考生对 MST 定义本质的理解——很多人以为边权变了 MST 就变，其实 MST 只取决于相对大小。

解题思维：看到题先想 MST 定义：连通所有点且边权和最小。构造法只有两种——Kruskal 按边权从小到大选不形成环的边，Prim 每次挑当前树外接的最小边。边权都加 C 后，相对大小 w_i + C < w_j + C 等价于 w_i < w_j，排序顺序完全不变，贪心策略完全一致，选出的边集自然不变。

陷阱拆解：错误选项 B 是典型"边权变了 MST 就变"的直觉陷阱。命题人利用考生对 MST 构造过程的表面记忆——以为算法会重新计算权重导致选边变化。其实无论算法内部怎么算，只要相对顺序不变，选出的边集就必然相同。题目最阴险的细节是"所有边"而非"部分边"，若只增加部分边，MST 确实可能变。

反命题思维：如果把"所有边统一增加"改成"部分边增加"，答案立刻变 B。刷到类似题先问：命题人想考我什么？是想考相对大小不变性，还是想考具体算法步骤？这道题只考前者，所以选项 A 正确。