城市规划题实战：必选边最小生成树与Kruskal全解析

GESP七级考完好几个同学来问这道城市规划题面读起来又长又绕街区、道路、预算、规划条件全揉在一起考场上第一眼都不知道该往哪个方向想。我复盘的时候重新整理了一遍这道题剥掉外壳之后本质上就是一个带必选边的最小生成树问题甚至比教材上的模板题只多了一个已经建好的道路不要重复计费的弯。这篇文章就顺着我的复盘过程来写从题目建模、算法选型、完整代码到考场上的细节坑一条线全部理清顺带把七级图论题常见的变体也聊透。1. 把城市规划翻译成图论语言1.1 拆掉题面的文字包装城市规划这类题目最擅长的就是用生活化名词把算法藏起来。我第一次读题也花了两分钟才反应过来所谓街区就是一个个节点候选道路就是带权边而已建成的道路就是不需要花钱的必选边。如果你在考场上读题读到规划部门希望任意两个街区都能通过规划后的道路互相到达这句话就要立刻警觉这就是图上所有点连通的意思。把题面里的名词翻译一遍整个模型立刻清晰很多题面说法图论含义算法中的角色街区节点并查集中的点已建成的道路必选边直接合并不计成本候选道路及造价可选边及边权参与Kruskal排序的边任意街区互通全图连通合并次数达到 n-1建设总费用最小边权和最小最小生成树的目标函数我经常跟准备等级考试的同学说读图论题就像做翻译题先别急着想算法先把每个名词对应到图上。这步做扎实了后面就是套模板的事。1.2 为什么这个模型落地后就是最小生成树如果所有道路都要从零开始建设那题目就是在所有候选道路中选出若干条使 n 个城市连通且总造价最小——这就是最小生成树的定义没有任何歧义。而这道题多了一层已经建成了一些道路很多人在这里卡住不知道怎么把必选边塞进算法里。处理方式其实很直线先把已建成的道路用并查集全部合并掉相当于把所有必选边先焊死在连通块里。这一步做完之后图中的连通块数量从 n 个减少到 n - cnt 个其中 cnt 是成功合并的次数。接下来把候选道路按造价从小到大排序用Kruskal逐条尝试合并连通块直到所有点连通。这个思路正确性的依据是最小生成树的一个经典性质如果预先固定若干条边必须保留那么包含这些边的最小生成树等价于先把这些边缩点再在缩点后的图上跑最小生成树。缩点后的图里每个节点就是一个已经连通的街区群候选道路变成连接这些街区群的边。Kruskal在这个缩点图上照常运行结果就是全局最优。所以你看必选边并没有让问题变难只是让你先做一轮并查集。1.3 先手动跑通一个五街区小例子为了后面验证代码我构造一个小数据人工推一遍全过程。设有 5 个街区编号 1 到 5已建成道路两条1-2 和 2-3。候选道路四条3-4造价 24-5造价 31-3造价 52-5造价 8第一步把已建成的 1-2、2-3 合并得到一个连通块 {1,2,3}合并次数为 2。此时还剩节点 4 和 5 在外面总共 5 个街区最终需要 4 次成功合并才能全连通所以还需要 2 次合并。第二步把候选边按造价排序3-42、4-53、1-35、2-58。第三步逐条尝试3-4节点 3 在 {1,2,3} 里节点 4 单独成块合并成功总费用 2合并次数变成 3。4-5节点 4 此时和 1、2、3 在同一连通块节点 5 单独成块合并成功总费用 235合并次数达到 4。合并次数已经等于 n-1算法提前结束输出 5。注意排在后面的 1-35和 2-58根本不需要再看因为所有点已经连通。这个例子的最优解是选 3-4 和 4-5 两条路总共花 5 个单位的预算非常直观。2. 最小生成树的两种写法Kruskal vs Prim2.1 Kruskal排序加并查集思维负担最小Kruskal的思路一句话就能说清把所有边按权值从小到大排序用并查集维护连通性逐条尝试能合并就合并直到生成树形成。这个算法最舒服的地方在于你几乎不需要思考当前该从哪个点出发只需要无脑排序加合并。在这道城市规划题里Kruskal还有一个天然优势必选边的处理完全无缝衔接。已建成的道路先合并候选道路再排序整个过程共享同一个并查集没有额外代码。而且Kruskal的编码错误点少只要并查集写对、排序写对主循环基本不会出错对考场心态很友好。时间复杂度方面排序是 O(q log q)其中 q 是候选道路数量并查集操作接近 O(1)总体复杂度由排序主导。对于七级考试的数据范围这个复杂度非常稳。2.2 Prim从点出发的视角什么时候才轮到它Prim的思路是从一个起点开始每次选择连接已选集合和未选集合的最小边把新点拉进来。它同样能求出最小生成树而且在稠密图上使用邻接矩阵的 O(n^2) 写法会比Kruskal更快。但在这道题里Prim有几个不太顺手的地方。首先是必选边的处理你得先把已建成道路涉及的节点提前拉进集合并且更新它们到集合的最小距离这个预处理比Kruskal的并查集合并要绕。其次如果考试时用堆优化的Prim代码量明显比Kruskal大出错概率也随之上升。除非题目给出的是邻接矩阵形式的稠密图而且 n 特别大、边数接近完全图否则我不太建议在七级考场用Prim。2.3 根据数据范围做选择题很多同学纠结到底背哪个算法我的答案是两个都得会但Kruskal作为首选Prim作为备选。做题之前先看数据范围情况推荐算法理由边数较少点也一般Kruskal代码短排序并查集稳定边数接近 n^2 的稠密图Prim邻接矩阵O(n^2) 不受边数影响需要记录生成树具体是哪几条边两者都行Kruskal直接输出结构体数组有必选边要先合并Kruskal并查集天然支持预合并动态加边在线询问任何基本算法都不能直接套需要扩展思路见第5章七级考试里出现裸最小生成树的概率不低数据范围一般不会故意卡死某一种算法。最稳妥的策略就是把Kruskal练到闭眼能写把Prim的堆优化理解到位考场上根据边数多少快速选择。3. 完整C代码与逐步验证3.1 代码结构三个部分各司其职这道题的完整代码分三块并查集封装、边的结构体定义、主流程。并查集单独抽象成结构体既方便必选边先合并又让主流程干净清晰。我把代码贴在下面注释写到位后面照着这个结构去默写基本不会乱。#include bits/stdc.h using namespace std; struct Edge { int u, v, w; }; struct DSU { vectorint fa, sz; DSU(int n) : fa(n 1), sz(n 1, 1) { iota(fa.begin(), fa.end(), 0); } int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } bool unite(int a, int b) { a find(a); b find(b); if (a b) return false; if (sz[a] sz[b]) swap(a, b); fa[b] a; sz[a] sz[b]; return true; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, p, q; cin n p q; // n: 街区数, p: 已建成道路数, q: 候选道路数 DSU dsu(n); int merged 0; for (int i 0; i p; i) { int u, v; cin u v; if (dsu.unite(u, v)) { merged; } } vectorEdge edges(q); for (int i 0; i q; i) { cin edges[i].u edges[i].v edges[i].w; } sort(edges.begin(), edges.end(), [](const Edge a, const Edge b) { return a.w b.w; }); long long ans 0; for (const Edge e : edges) { if (merged n - 1) break; if (dsu.unite(e.u, e.v)) { ans e.w; merged; } } if (merged n - 1) { cout ans \n; } else { cout -1 \n; } return 0; }这里有个细节值得说明merged 记录的是成功合并的次数。一开始 n 个街区各自独立全部连通需要正好 n-1 次合并。已建成道路每成功合并一次merged 加一候选道路每成功合并一次merged 也加一。最后比较 merged 和 n-1就能判断是否所有街区连通这比统计连通块数量再比较块数更直观也少写代码。3.2 把1.3的样例喂给代码我用刚才那个五街区例子来走一遍代码逻辑。输入为5 2 4 1 2 2 3 3 4 2 4 5 3 1 3 5 2 5 8并查集初始状态是五个独立集合。先处理两条已建成道路合并 1-2 后 merged1合并 2-3 后 merged2当前连通块为 {1,2,3}、{4}、{5}。然后排序候选边得到 (3,4,w2)、(4,5,w3)、(1,3,w5)、(2,5,w8)。主循环里第一条边 3-4 合并 {1,2,3} 和 {4}merged3ans2。第二条边 4-5 合并新的大块和 {5}merged4ans5。此时 merged 等于 n-1循环直接 break。输出 5和手推结果一致。3.3 复杂度与空间占用空间上并查集两个数组都是 n1 大小候选边数组 q 条没有任何多余结构。时间上排序 O(q log q)并查集操作近似 O(1)整体跑得飞快。这道题如果 q 最大到十几万排序依然是绝对主导但绝对时间完全可控。C 的 iostream 关掉同步之后读入几万条边毫无压力。如果你在考场上用的是比较老的编译器记得把 sort 的比较函数写成 lambda 或者普通函数不要每次在循环里重排。4. 考场上的几个致命细节4.1 已建成道路不能重复计费这是这道题最大的一个坑。很多人一看到最小生成树就激动把已建成道路和候选道路一起塞进边集排序结果建好的路也被当成候选路计算了一次造价。题目问的是额外还需要多少预算已建成道路花的钱早就花掉了不应该计入答案。我习惯的做法是输入的时候就分成两段处理。已建成道路立刻并查集合并并且用 merged 计数不存进边数组。候选道路才存进 vector参与后续排序。这样代码逻辑上就彻底杜绝了重复计费的可能。4.2 并查集的路径压缩与按秩合并为什么不能省并查集如果不写路径压缩find 的复杂度会退化到 O(n)整个算法直接退化成 O(n^2)数据一大就超时。路径压缩就是 find 里那句fa[x] find(fa[x])代码只有一行但作用巨大。按秩合并上面的 sz 数组则是保证树高尽量小两种优化搭配在一起均摊复杂度接近常数。我在教学里见过不少同学为了省事只写路径压缩不写按秩合并其实也能过因为路径压缩单独使用性能已经很好了。但既然模板完整写下来就多三行代码建议还是写上万一遇到极端数据按秩合并能提供额外保障。4.3 排序运算符和long long的故事结构体排序有两种写法重载小于号或者用 sort 传 lambda。两种都行但有一个共同的坑——比较函数必须严格弱序也就是说相等的时候要返回 false。如果你重载时把a.w b.w写成了a.w b.wsort 的行为就没有定义轻则排序错误重则直接崩溃。这种错误在样例数据上往往测不出来只有大数据才会爆发特别恶心。另一个坑是答案类型。n 个街区算全部连通的极限情况候选道路的造价如果每条都很大总费用可能超过 int 范围。虽然七级题一般不会故意卡这里但long long ans是零成本的保险。输入输出用%lld或者直接 cout别写混了。4.4 边界只有一个街区、全部已连通、无解这三种边界情况代码里其实都已经自然处理了但考场上要心里有数。n1 时一个街区当然已经连通不需要任何道路。已建成道路输入中如果出现 1 1 这种自环实际不会并查集的 unite 会返回 false不影响。全部已连通时merged 一开始就是 n-1主循环第一轮就会 break输出 0。无解的情况就是候选道路全部用完也没能达到 n-1 次合并最后输出 -1。我建议考试时专门构造这三个边界用例来测自己的代码。学会自己造边界数据是信息学考试里性价比最高的习惯之一。5. 从这道题延伸出去七级图论复习指南5.1 城市规划常见的四种变体最小生成树的题目特别适合包装成各种规划题我总结几种常见的变体供你平时训练时对照变体一最小瓶颈生成树。要求选出的道路中最大造价尽可能小而不是总造价最小。注意一个经典结论最小生成树同时也是最小瓶颈生成树所以直接用Kruskal就能解。变体二必须经过某些关键街区。在候选道路外额外指定若干节点要求它们最终必须连通。实际做法和必选边类似把关键节点先合并成一个块。变体三检查生成树是否唯一。把边按权值分组处理每一组内先统计能合并的数量再实际合并如果存在多条同权边可选就需要额外判断。变体四次小生成树。在最小生成树的基础上枚举每条非树边替换树上的边维护最大值边求出次优解。七级考这个概率不大但如果复习到位遇到就稳赚。5.2 建模能力才是七级真正的考点GESP七级的图论题说实话算法本身并不难难的是把文字题面翻译成图论模型。像城市规划这种题核心就考两点你能不能从任意互通嗅到连通性以及能不能从费用最小嗅到最优化。这两点一旦翻译出来剩下的就是背模板的功夫。所以我复习图论有一个习惯拿到一道题先不看题解花十分钟把题面里的名词全部列出来强制要求自己写出对应的图论概念。这个训练做满二三十道题之后再遇到陌生题面就不会慌了因为你已经形成了一套翻译套路。5.3 给后面考生的刷题建议如果你正在准备下一期七级考试我的建议是把最小生成树的Kruskal模板练到闭眼默写并且专门练习必选边可选边这种两层输入的变式。每道题写完都自己构造三组额外数据一组边界n1、已经全连通、无解一组随机数据用暴力验证一组大数据测时间。对拍的习惯越早养成越好它能帮你发现所有样例测不出来的潜在问题。最后再分享一个小技巧考场上如果时间充裕写完代码先把输出格式检查一遍因为无解输出 -1这种要求最容易漏看。这份小细节可能就会帮你多拿一个测试点的分数。