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 数组要开 n+1，并且用 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 完整代码（带注释）
下面是一份完整的 C++17 参考实现，核心逻辑只有二十多行，注释已经写得比较详细，可以直接照着理解。如果你平时习惯递归版 find，也可以用递归写法，两者在数据范围不大时性能差别可以忽略。
#include <bits/stdc++.h> using namespace std; struct Edge { int u, v, w; // 按边权从小到大排序 bool operator < (const Edge& other) const { return w < other.w; } }; vector<int> 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; vector<Edge> 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 手写一组小数据验证算法
考场上写完算法，最怕自我感觉良好，一交全错。我当时养成的习惯是立刻构造一组能徒手算出答案的小数据，跑一遍程序核对结果。这里给出一组自测样例，用来验证上面的实现逻辑：
假设 n=5，m=5，k=2，边为： 1-2 费用 1 2-3 费用 2 3-4 费用 3 4-5 费用 4 1-5 费用 10
目标是从 5 个连通块减到 2 个，需要成功合并 3 次。按费用从小到大排序，依次考虑：1-2 合并，连通块变成 4；2-3 合并，连通块变成 3；3-4 合并，连通块变成 2，已经达到 k，立即停止。累计费用 1+2+3=6。如果程序输出 6，说明主流程基本正确。如果输出 10 或者把后续边都加上，那就要检查是不是没有在 cnt==k 时及时退出。
再测一组无解数据：n=4，m=1，k=2，只给一条边 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^2，Kruskal 的排序成本会变高。此时可以考虑 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^5，m 不超过 10^5，总费用理论上能到 10^10，int 根本存不下。我在训练时曾经因为这个问题错了一次以后，现在只要看到“累计花费”，一律先开 long long，省心很多。
5. 把这题吃透后，能迁移到哪些题目
5.1 最小生成树变体的特征
做完“建造”这道题，值得停下来总结：怎样一眼识别出这类题可以用 Kruskal 变形做？我的经验是看三个关键词：一是“有一些点/城市/节点”，二是“有一些可选的连接/道路/桥”，三是“要求分成若干块/连通块/区域，使总费用最小”。只要这三个条件同时出现，大概率就是最小生成树或最小生成森林题。比如经典的“口袋的天空”“连接格点”都是同一个家族。
变式变化主要集中在目标区域的个数上。有时候问的是把所有点连成一个连通块，那么答案是生成树，边数是 n-1；有时候问的是分成 k 个连通块，那么边数是 n-k；还有的时候不是问“分成多少块”，而是问“某几个重要节点必须连通”，那就要用带权并查集或者虚拟点技巧。但无论怎么变，核心思路都是：先想清楚成功合并一次会让答案发生什么变化，再用 Kruskal 贪心选出必要边。
5.2 当“建造”变成“必须连成几个大区域”
如果题面继续升级，比如要求每个连通块内部必须包含至少一个“资源点”，或者每个连通块的规模不能超过某个限制，那就不能只用普通并查集解决了，可能要引入带权并查集维护附加信息，或者结合二分答案验证可行性。但打好基础的话，B4451 这道四级题已经能帮你建立“用并查集维护动态连通性”的直觉，后续学带权并查集时会顺很多。
另一种常见变形是反向思考：一开始所有路都是通的，现在要拆掉一些边，让图变成 k 个连通块且拆除费用最大/最小。这种题通常可以转换成“保留尽量便宜的生成森林”，再拿总边权减去保留费用，本质上还是同一套模型。平时训练时多做一步“我把这题转化成 Kruskal 的哪一步”的总结，比单纯刷题更有效。
5.3 备考 GESP 四级的训练建议
如果距离考试还有一段时间，我建议把“建造”当作一道母题，按这样的顺序训练：先用 10 分钟自己写一遍并查集模板，再把“分成 k 个连通块”的条件改成“全部连通”，对比两个版本的循环终止条件；最后给代码随机生成一些小数据，用暴力枚举或者肉眼验证结果，体会贪心过程。熟练之后，再去做几道 Kruskal 真题，基本上见到“建造”类题目就不会再发怵。
我个人在实际备考复盘时会准备一个小本子，专门记这种“同一模型不同马甲”的题。B4451 被写上去的时候，旁边就注释着一行字：“看到建造、连通、最少花费，先想并查集能不能减块。”后来我参加模拟赛遇到类似题，基本一看到题目背景就能定位到算法，省下大量读题时间。这种题考的不是你会不会编复杂的程序，而是你有没有把基本功练到顺手拈来的程度，所以别嫌它简单，能稳稳拿满分的题才是考场上真正的底牌。
