GESP 四级出题风格里我印象最深的一类题是“名称听起来像模拟实际考的是图论板子”的题。比如 B4451 [GESP202512 四级] 建造光看“建造”两个字很容易让人以为要写一个盖房子、铺地板的模拟可真到考场上拆开算多数解法最终都收敛到并查集和 Kruskal 的变式把零散节点合并成若干个连通块算最小费用。考前练过这类模型的人基本等于拿到一道模板改编题没练过的人很容易被题名带偏一路往区间贪心、枚举子集甚至更高阶的动态规划方向硬想反而把自己绕进去。这篇文章就把我当时复盘这道题的完整过程写出来包括题眼拆解、贪心证明、能直接抄的 C 实现以及考场调试时常踩的几个坑。适合正在备 GESP 四级、或者想用最小生成树思路刷普及组图论题的选手参考。1. 先从“建造”这两个字读出题眼1.1 题面在问什么把连通块数量降下去我按原题思路把题意抽象成这样一个模型有 n 个城市m 条“可以修建”的道路每条道路连接两个城市并且有一个修建花费。最终目标是把所有城市划分成恰好 k 个互相连通的区域区域内任意两个城市都能通过已修道路互相到达。问最少需要花多少钱来完成建造无解时按题目约定输出 impossible。把这句话再翻译一遍就是初始时一个城市单独是一个连通块所以有 n 个连通块。修建一条路本质是选择两个当前还不在同一个连通块里的城市把它们所在的块合并成一个连通块数量减少 1。要从 n 个块变成 k 个块恰好需要做 n-k 次成功合并。于是问题从“怎么修路”变成了“按什么顺序合并连通块能让总花费最小”。这个转换是整个题目的第一个分水岭没有想清楚这一步代码写出来基本会变成一锅粥。1.2 看到“最少费用”先想到哪几条路如果要在一个图里让所有点都连通并且总边权最小大家第一反应都是最小生成树。这里虽然目标不是所有点连通成一个整体而是 k 个整体但底层逻辑完全一样只需要保留能让连通块数量从 n 减少到 k 的那些边。换句话说答案就是原图的一棵“最小生成森林”这个森林由恰好 n-k 条边组成。为什么是 n-k 条因为初始 n 个孤立点每加入一条不构成环的边会让连通块数量减少 1最终要留下 k 个连通块所以中途一定加入 n-k 条合法边。选满了这个数量之后继续加边只会让连通块数量更少不再满足“恰好 k 个区域”的约束。到这里解题方向就从“建造”收敛到了“在图上选 n-k 条不成环的最低费用边”。1.3 真正的考点并查集 Kruskal 贪心由前面的抽象算法名基本已经呼之欲出Kruskal。先把所有边按花费从小到大排序然后从小往大扫用并查集判断一条边连接的两端是否已经在同一个连通块里。如果不在同一个块就修这条路并合并两个块累计费用如果已经在同一个块说明这条边会形成环在生成森林里没有意义直接跳过。重复这个过程直到成功合并出 n-k 条边。顺带说一句GESP 四级这套考纲里并查集本身就可能作为独立知识点出现而“建造”这道题巧妙地把并查集放进了最小生成树的应用场景里。所以备考时只背并查集的 find 和 unite 模板是不够的必须理解它服务于什么目标、怎么参与贪心决策。这也是为什么我建议把这道题当作一个经典例题精刷而不是当普通练习匆匆过一遍。2. 算法推演为什么最小的“安全边”组合就是答案2.1 把问题看成生成森林的生长过程最开始所有城市都是一棵只有根节点的树没有任何边。Kruskal 的过程可以想象成一个森林逐渐合并的过程每次取一条当前花费最小的边如果它连接了两棵不同的树就相当于把两棵树用一根树枝“接”起来森林里树的棵数减一。如果直接求最小生成树答案需要的边数是 n-1最后森林只剩一棵树。可这道题求的是“k 棵树的最小生成森林”所以不需要把森林合并到只剩一棵树减到 k 棵的时候就该停手。这个区别必须时刻记在脑子里否则容易在循环里多加边最后输出一个连接得过多、费用偏大的错误结果。2.2 贪心选择为什么不会翻车很多人学 Kruskal 的时候只知道“按边权排序从小到大加边”但很少深究为什么这个贪心一定正确。遇到变式题如果只停留在背模板的层面稍微把目标从 1 棵生成树改成 k 棵生成森林心里就会发慌。原理可以这样理解在任何一步当前所有城市已经被若干条已选边划分成了若干个连通块。接下来要减少一个连通块就必须选一条横跨两个连通块的边。假设有一条候选边 e它连接的两个块之间当前还没有被选中的边连通那么所有不包含 e 的合法方案里这两个块最终也一定要靠某条边连起来那条边的花费如果比 e 小早就该被扫到了如果比 e 大那换成 e 只会更便宜。所以每一步选“当前能合并两个块的最小边”都不会让答案变差。一步一步推下去贪心策略自然成立。这个论证和最小生成树里的“切分定理”是同一套逻辑只不过切分出来的不是单独的子树而是若干个并查集集合。Kruskal 的优雅之处就在于它不需要我们显式判断哪条边连接的两个块之间有没有更便宜的替代路径排序后顺序扫描加上并查集判环就自动完成了这个贪心筛选。2.3 并查集维护连通块数目的关键数据结构整个过程最核心的数据结构就是并查集。初始化时让每个点的父节点指向自己连通块数量 cnt n。每尝试一条边 u,v先 find(u) 和 find(v)如果根不同说明 u 和 v 不在同一个块内这是合法合并执行 fa[find(u)] find(v)然后 cnt--。如果根相同说明它们已经在同一个块里加上这条边会让当前生成森林出现环必须舍弃。这里有个容易被忽略的点并查集只负责维护连通关系不直接维护答案费用。真正的答案费用是在成功 union 时把这条边的权值累加进 ans。很多初学者会误把每条边都累加导致最后答案远大于正确值这是考场上最冤的失分点之一。3. C 实现考场可以直接参考的写法3.1 从输入到结构体的一气呵成存储边信息时建议用结构体记录 u、v、w 三个字段。排序时直接按 w 从小到大排所以可以在结构体里重载小于运算符。关于变量类型n 和 m 的范围如果不算大int 足够但 ans 建议直接用 long long。原因很简单如果 m 达到十万或者更大边权累加后很容易超过 int 上限GESP 和普及组题里虽然不常卡这个点但养成开 long long 的习惯能省掉很多无所谓的 debug 时间。输入输出方面用 cin 完全没问题但记得在 main 开头加上 ios::sync_with_stdio(false) 和 cin.tie(nullptr) 两行避免数据量稍大时被 I/O 拖速度。如果真的遇到大数据也可以改用 scanf不过在考场环境下优先保证代码简洁、不容易写错再考虑极限性能。3.2 主循环里最容易写错的三处细节第一个细节是循环的终止条件。应该是 cnt k每成功合并一次 cnt 减一一旦 cnt k 就停下来输出答案。如果写成了遍历所有边就会继续合并导致最后的连通块数量小于 k答案会比最优值偏大即使数据弱能过逻辑上也不严谨。第二个细节是并查集初始化范围。城市编号通常从 1 到 n所以 fa 数组要开 n1并且用 iota(fa.begin(), fa.end(), 0) 把每个位置初始化成自己。如果习惯 for 循环就写 for (int i 1; i n; i) fa[i] i; 注意一定不要从 0 开始覆盖掉了不该动的边界。第三个细节是判断无解的时机。扫描完所有边之后如果 cnt 仍然大于 k说明能用来合并的合法边不够多此时输出 impossible。注意有些题目要求输出 -1但“建造”这类题里约定是 impossible最好在写程序前先把输出格式盯清楚别在这里因为字符串拼写错误白丢分。3.3 完整代码带注释下面是一份完整的 C17 参考实现核心逻辑只有二十多行注释已经写得比较详细可以直接照着理解。如果你平时习惯递归版 find也可以用递归写法两者在数据范围不大时性能差别可以忽略。#include bits/stdc.h using namespace std; struct Edge { int u, v, w; // 按边权从小到大排序 bool operator (const Edge other) const { return w other.w; } }; vectorint fa; // 查找根节点带路径压缩 int find(int x) { if (fa[x] x) return x; return fa[x] find(fa[x]); } // 合并两个集合成功合并返回 true bool unite(int a, int b) { a find(a); b find(b); if (a b) return false; fa[a] b; return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, k; cin n m k; vectorEdge edges; for (int i 0; i m; i) { int u, v, w; cin u v w; edges.push_back({u, v, w}); } // 贪心基础按花费从小到大处理 sort(edges.begin(), edges.end()); fa.resize(n 1); for (int i 1; i n; i) fa[i] i; int cnt n; // 当前连通块数量 long long ans 0; // 总花费 for (const Edge e : edges) { if (cnt k) break; // 已经达到目标块数不用再修路 if (unite(e.u, e.v)) { // 两端不在同一连通块 ans e.w; cnt--; } } if (cnt k) cout ans \n; else cout impossible\n; return 0; }这段代码的复杂度是排序的 O(m log m)并查集部分接近 O(m α(n))。如果 n 给到 1e5、m 给到 2e5跑起来也毫无压力属于典型的“数据范围看着吓人实际模板一交就过”的题。4. 踩坑实录与验证技巧4.1 手写一组小数据验证算法考场上写完算法最怕自我感觉良好一交全错。我当时养成的习惯是立刻构造一组能徒手算出答案的小数据跑一遍程序核对结果。这里给出一组自测样例用来验证上面的实现逻辑假设 n5m5k2边为 1-2 费用 1 2-3 费用 2 3-4 费用 3 4-5 费用 4 1-5 费用 10目标是从 5 个连通块减到 2 个需要成功合并 3 次。按费用从小到大排序依次考虑1-2 合并连通块变成 42-3 合并连通块变成 33-4 合并连通块变成 2已经达到 k立即停止。累计费用 1236。如果程序输出 6说明主流程基本正确。如果输出 10 或者把后续边都加上那就要检查是不是没有在 cntk 时及时退出。再测一组无解数据n4m1k2只给一条边 1-2费用 100。初始 4 个连通块只能合并一次变成 3达不到 2正确输出应该是 impossible。这两组数据都不大却能把“提前退出”和“无解判断”两个最容易出错的地方都覆盖到。4.2 连通块数没达到 k却在循环里提前结束有个场景很迷惑看起来 cnt 在递减但最后输出 impossible。多数原因是并查集合并时机判断错了。比如一条边连接的两个城市虽然在原始输入里编号不同但在之前的合并中已经同属一个集合那么这条边就不会让 cnt 减少。如果题给图中有大量这种“废边”实际可用的有效边数量可能远小于 m。所以不要以为 m 很大就一定能修到 k 个块必须最后检查一次 cnt。还有一种可能是初始化时把编号写成了从 0 到 n-1。GESP 题面里如果城市编号是 1-based而你的并查集数组只初始化了 0 到 n-1那 find(n) 会访问到默认值为 0 的位置导致错误合并整个 cnt 计数全乱。4.3 被卡时间或空间先看这组复杂度数据有些同学担心 Kruskal 会超时其实完全没必要。排序是 O(m log m)而并查集经过路径压缩后每次操作的均摊复杂度接近常数。假设 m 是 2e5排序也只需要几十毫秒级别这已经覆盖绝大多数普及组和 GESP 四级的数据范围。如果你看到 n 有 1e5 但 m 也有 1e5不要慌这恰恰是 Kruskal 最擅长的场景。反而是如果题目变成稠密图n 只有 2000 但 m 接近 n^2Kruskal 的排序成本会变高。此时可以考虑 Prim 的 O(n^2) 写法。不过 GESP 四级一般不会故意出这种卡排序的题先把 Kruskal 模板默写熟练性价比最高。4.4 我的三个考场坏习惯第一个坏习惯是打印答案前不检查输出格式。impossible 这种单词容易拼成 impossable虽然考试环境不会因此编译报错但判题结果一定是 WA。建议在写题目之前就把输出字符串直接从题面复制到代码注释里。第二个坏习惯是用递归 find 但不加路径压缩。最坏情况下并查集树会退化成一条链find 一趟可能 O(n)加上 m 次操作后程序会明显变慢。递归写法本身没问题但必须写 fa[x] find(fa[x]) 这句压缩。第三个坏习惯是没把 ans 定义成 long long。其实很多类似题的数据范围都写着边权不超过 10^5m 不超过 10^5总费用理论上能到 10^10int 根本存不下。我在训练时曾经因为这个问题错了一次以后现在只要看到“累计花费”一律先开 long long省心很多。5. 把这题吃透后能迁移到哪些题目5.1 最小生成树变体的特征做完“建造”这道题值得停下来总结怎样一眼识别出这类题可以用 Kruskal 变形做我的经验是看三个关键词一是“有一些点/城市/节点”二是“有一些可选的连接/道路/桥”三是“要求分成若干块/连通块/区域使总费用最小”。只要这三个条件同时出现大概率就是最小生成树或最小生成森林题。比如经典的“口袋的天空”“连接格点”都是同一个家族。变式变化主要集中在目标区域的个数上。有时候问的是把所有点连成一个连通块那么答案是生成树边数是 n-1有时候问的是分成 k 个连通块那么边数是 n-k还有的时候不是问“分成多少块”而是问“某几个重要节点必须连通”那就要用带权并查集或者虚拟点技巧。但无论怎么变核心思路都是先想清楚成功合并一次会让答案发生什么变化再用 Kruskal 贪心选出必要边。5.2 当“建造”变成“必须连成几个大区域”如果题面继续升级比如要求每个连通块内部必须包含至少一个“资源点”或者每个连通块的规模不能超过某个限制那就不能只用普通并查集解决了可能要引入带权并查集维护附加信息或者结合二分答案验证可行性。但打好基础的话B4451 这道四级题已经能帮你建立“用并查集维护动态连通性”的直觉后续学带权并查集时会顺很多。另一种常见变形是反向思考一开始所有路都是通的现在要拆掉一些边让图变成 k 个连通块且拆除费用最大/最小。这种题通常可以转换成“保留尽量便宜的生成森林”再拿总边权减去保留费用本质上还是同一套模型。平时训练时多做一步“我把这题转化成 Kruskal 的哪一步”的总结比单纯刷题更有效。5.3 备考 GESP 四级的训练建议如果距离考试还有一段时间我建议把“建造”当作一道母题按这样的顺序训练先用 10 分钟自己写一遍并查集模板再把“分成 k 个连通块”的条件改成“全部连通”对比两个版本的循环终止条件最后给代码随机生成一些小数据用暴力枚举或者肉眼验证结果体会贪心过程。熟练之后再去做几道 Kruskal 真题基本上见到“建造”类题目就不会再发怵。我个人在实际备考复盘时会准备一个小本子专门记这种“同一模型不同马甲”的题。B4451 被写上去的时候旁边就注释着一行字“看到建造、连通、最少花费先想并查集能不能减块。”后来我参加模拟赛遇到类似题基本一看到题目背景就能定位到算法省下大量读题时间。这种题考的不是你会不会编复杂的程序而是你有没有把基本功练到顺手拈来的程度所以别嫌它简单能稳稳拿满分的题才是考场上真正的底牌。