第一次看到“ZJUKY132 还是畅通工程”这个题号时我先愣了两秒前面一长串编号后面跟着“还是畅通工程”。这个“还是”字很有意思它明明白白告诉我这是系列题里的又一关不是第一次碰“畅通工程”了。如果读者你做过数据结构或算法课里的“畅通工程”估计已经能猜到七八成这类题把“在城镇之间修路让任意两地连通”抽象成图论问题第一版考并查集这一版考的是最小生成树。想把这题完整拿下光套模板还不够输入边界、并查集实现细节、样例之外的隐藏数据每一项都可能把你挂在一个WA上反复摩擦。这篇文章写给三拨人一是正在做课程作业、想弄懂“还是畅通工程”到底在问什么的学生二是刷题时想系统整理“最小生成树”模板的同学三是工作中偶尔遇到连通性设计问题、想把图论算法落到工程场景的开发者。我会按自己的做题习惯先讲题目模型再讲为什么是Kruskal或Prim然后给完整可跑的代码最后把那些“题目没写但你一定会踩”的坑逐个点一遍。1. 先看懂题号与题目家族ZJUKY132到底在考什么1.1 题号不重要重要的是它属于“畅通工程”系列先说题号。ZJUKY132看起来像校内OJ的题目编号或课程作业代号我没法百分百确认具体是哪所学校、哪个题库但这不影响解题思路。我见过类似格式的题号出现在很多课程作业清单里一般规律是“学校缩写课程缩写编号”甚至有些老师直接拿现成题库里的题号当作业号发。所以与其在这串字符上花时间不如把注意力放在标题后半段——回到“畅通工程”这个系列。“畅通工程”几乎是中文算法教学里的固定梗了连着出了好几个版本。我第一次做这个系列时还在纳闷修路明明是土木工程的事怎么跑进算法课里来了后来才反应过来题目里说的城镇、道路、成本全是图论模型的道具真正要练的是连通性判定和最小生成树。想明白这一点后面做题的节奏就顺多了。1.2 一张表理清“畅通工程”三兄弟为了方便对照我把最常见的三个版本放在一起看。题目名称输入特点解决目标核心算法畅通工程给定已经存在的若干条道路还需要修几条路才能让所有城镇连通并查集数连通分量还是畅通工程给出所有候选道路的修建成本选哪些路修建使总成本最小且全图连通最小生成树Kruskal/Prim继续畅通工程部分道路已经修好剩余给出成本在已有基础上继续修使总成本最小最小生成树先合并已有的边第一次做“畅通工程”时你只要判断连通性就好n个城镇m条已建道路用并查集把已经连通的分组合并最后数一数有几组输出“组数-1”。因为要从k个不连通的分量变成一个连通整体最省的办法是修k-1条路而题目只问你数量不问你具体修哪几条。到了“还是畅通工程”输入完全变了它把任意两个城镇之间可能修路的成本都给你让你挑出若干条让整个图连通同时总成本最小。注意这里没有要求“修的路越少越好”只要求“总成本最小”。所以有可能出现一种反直觉的结果为了省下一条高价路宁愿多修两条便宜路。这类“选边”问题答案就不再是并查集能直接算出来的了。1.3 从“修路”到图论模型的翻译我习惯在写代码前先做一次“翻译”城镇对应图的顶点两个城镇之间“可以修路”对应一条候选边成本对应边权。题目保证最终一定有可行方案的时候我们要输出的就是最小生成树的权值总和如果题目版本没有保证连通那还要在跑完算法后检查一下所有点是否都已经并到一起。这道题的名字里还有“还是”两个字说明它是上一题的加强版。做加强版题的正确姿势不是把上一个版本的代码拿来改两行就交而是先把两个版本的差异写出来上一版问你“修几条”这一版问你“花多少钱”。这两个问题的算法模型完全不同强行用并查集只能拿到部分分甚至可能连样例都解释不了。我从身边同学的情况看大多数卡在这道题上的人都不是不会写Kruskal而是压根没意识到题目已经从“计数”切换到了“最优化”。2. 为什么第一问用并查集第二问必须换成最小生成树2.1 第一代畅通工程连得上就行先回顾一下“畅通工程”的并查集解法每个集合代表一片已经连通的城镇每读入一条路就把两个端点所在集合合并最后统计有效合并次数实际连通分量数就是 n - 合并次数。如果这个数量大于1说明有分量数-1条路以外的缺口理论上修分量数-1条路就能全部连通。这个思路只能回答“最少还要修几条”回答不了“修哪几条最便宜”。因为当每条路有不同成本时修最少的几条并不等于花最少的钱甚至可能出现“多修一条便宜路、少修一条贵路”整体更划算的情况。举个极端例子两个城市的直连路要100万但绕道相邻城市、拆成两段路各30万总成本60万比直连便宜。这种时候如果只按“最少条数”去选反而选到了更贵的方案。2.2 还是畅通工程连上还要代价最小“还是畅通工程”把成本这个维度加进来后问题性质就变了。它不是找任意一条路把集合连起来而是在所有候选边里选一个“无环、连通、总权最小”的子图。这个子图恰好就是最小生成树。为什么一定是“树”而不是更复杂的图因为只要有环从环上拆掉一条边图仍然连通总权只会变小或不变。所以最优解一定没有环而且为了连通它必然有 n-1 条边刚好构成一棵树。这个性质也解释了为什么我们不需要考虑“多修路变相降低总成本”的情况——多出来的路必然成环而环上的路是可以拆掉的拆掉之后连通性不受影响成本还会下降。2.3 Kruskal贪心成立的理由最小生成树有两个经典算法一个Kruskal一个Prim。Kruskal的想法特别朴素把边按成本从小到大排序从最便宜的开始一条一条尝试加入如果加入后不形成环就保留它如果形成环就跳过。直到所有顶点都在同一个连通分量里。这个贪心不是碰运气它基于一个著名的“安全边”性质在一个无向连通图里把顶点集合切成任意两部分跨越这两个集合的所有边中权值最小的一条一定可以被某棵最小生成树选入。Kruskal每加入一条边实际就是在当前森林的两个连通分量之间选择跨边的最小值所以每一步都是安全的。反过来说如果一条边加入后形成环它一定是当前环上的一条边而环上最大的边不可能属于任何一棵最小生成树跳过它不会损失最优解。我当初第一次听的时候也觉得绕后来用一个简单的例子来记4个城市A-B成本1B-C成本2C-A成本3还有一条B-D成本100。如果贪心先把A-B、B-C选进去A-B-C是一条链没问题再加入C-A会形成三角形环边权3是整个环里最大的跳过它不会影响连通。这个例子让我后来再也没忘过Kruskal为什么敢跳过“成环的边”。顺带说一句Prim走的是另一条路从一个点出发不断把“当前连通集合”和“外部点”之间最短的边拉进来。它每一步选的也是跨边最小值所以同样基于安全边性质。两种算法只是从边的角度和点的角度分别切蛋糕最后得到的答案一定一致。3. 手把手实现Kruskal从定义边到跑通样例3.1 准备工作三条关键数据结构实现Kruskal需要三样东西边的存储结构、并查集、排序。第一边的存储结构。经典写法是定义结构体包含u、v、w三个字段。u和v是两个端点编号w是成本。这个结构体写得越简单越好不需要附带乱七八糟的索引信息因为后面排序只需要参考w。第二并查集。它负责回答“两个点当前是否已经在同一个连通分量里”以及“如何把两个分量合并”。这个数据结构写错的代价比排序还大因为它一旦出问题整个主循环的判断就全乱了后面单独说。第三排序。把所有边按w升序排列这是Kruskal的主心骨。排序都写不对的话后面的算法没有任何正确性可言。3.2 主流程的四个关键点把主循环拆开其实只有四步初始化并查集每个点是一个独立分量连通分量数量cntn。按权值从小到大遍历所有边。检查边的两个端点find是否相同不相同说明这条边连接了两个不同分量加入它不会成环执行合并累加答案cnt减1。当cnt等于1时说明所有点已经连通提前结束循环。为什么可以提前结束因为边已经按权值从小到大处理当前结果已经是最小生成树的一部分后面即使还有便宜的边不可能有因为已经排过序也不需要再看了。提前break不只是优化还能避免在无意义的大边权上浪费时间。3.3 C参考代码下面这个版本我按最常见的题面来写先读nn为0结束随后给出n(n-1)/2行每行u v w表示一条候选道路的成本。如果哪天你遇到的题面第一行给的是m而不是这种固定行数只需要把 m n * (n - 1) / 2 改成先读取m即可。#include bits/stdc.h using namespace std; struct Edge { int u, v, w; bool operator(const Edge other) const { return w other.w; } }; vectorint parent, rnk; int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } bool unite(int a, int b) { a find(a); b find(b); if (a b) return false; if (rnk[a] rnk[b]) swap(a, b); parent[b] a; if (rnk[a] rnk[b]) rnk[a]; return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; while (cin n) { if (n 0) break; int m n * (n - 1) / 2; vectorEdge edges(m); for (int i 0; i m; i) { cin edges[i].u edges[i].v edges[i].w; } sort(edges.begin(), edges.end()); parent.resize(n 1); rnk.assign(n 1, 0); for (int i 1; i n; i) parent[i] i; int cnt n; int ans 0; for (const Edge e : edges) { if (unite(e.u, e.v)) { ans e.w; cnt--; if (cnt 1) break; } } cout ans \n; } return 0; }这段代码我在N不超过1000的范围内实测过排序是最主要的耗时点其余逻辑基本是常数级。如果你的OJ版本要求题目可能不连通循环结束后cnt大于1时应该输出-1或题目指定的值不要直接输出ans。3.4 Python简化版Python写起来更短但思路完全一样class DSU: def __init__(self, n): self.p list(range(n 1)) self.r [0] * (n 1) def find(self, x): while self.p[x] ! x: self.p[x] self.p[self.p[x]] x self.p[x] return x def union(self, a, b): ra, rb self.find(a), self.find(b) if ra rb: return False if self.r[ra] self.r[rb]: ra, rb rb, ra self.p[rb] ra if self.r[ra] self.r[rb]: self.r[ra] 1 return True def solve(): import sys data sys.stdin.read().strip().split() it iter(data) out [] for token in it: n int(token) if n 0: break edges [] for _ in range(n * (n - 1) // 2): u int(next(it)) v int(next(it)) w int(next(it)) edges.append((w, u, v)) edges.sort() dsu DSU(n) cnt, ans n, 0 for w, u, v in edges: if dsu.union(u, v): ans w cnt - 1 if cnt 1: break out.append(str(ans)) sys.stdout.write(\n.join(out)) if __name__ __main__: solve()在Python里注意别用递归find应对特别大的树虽然这题N通常不大但一旦路径压缩没写好最坏情况可能退化成一条链递归深度会很难看。上面这种whilepath compression的写法更稳。3.5 复杂度到底是多少Kruskal的复杂度由两部分组成排序O(E log E)并查集的合并与查询接近O(E α(n))其中α(n)是反阿克曼函数在实际数据范围内可以认为几乎不变。所以整体就是排序主导。对于En(n-1)/2这种完全图级别当n1000时E约5×10^5排序完全没问题如果n到10^5这种输入模式本身就不成立需要换思路。Prim的复杂度是O(V^2)邻接矩阵版或O(E log V)堆优化版。在稠密图、n比较小的时候Prim的朴素写法常常更省事在稀疏图上Kruskal通常实现简单且不容易写错。为了方便现场决策我常用的一个对比表维度KruskalPrim朴素/堆优化核心思路按边权从小到大选边从起点出发扩展连通块需要的数据结构边集数组并查集邻接矩阵/邻接表堆时间复杂度O(E log E)O(V^2) 或 O(E log V)更适合稀疏图、边能排序稠密图、邻接矩阵方便代码量较小朴素版小堆优化版稍大难点并查集的正确性堆更新、去重边对于“还是畅通工程”这种把完全图所有边都给出来的题目两种算法都能过。我自己的习惯是优先写Kruskal因为它的输入模型和题面“给出若干条候选路”是完全对应的不需要手动建邻接矩阵。4. 样例之外全是坑从WA到AC的排查清单4.1 多组数据与输入格式的分歧“还是畅通工程”这种题几乎都是多组测试输入以n0结束。最容易翻车的地方有两个一是忘了用while循环处理多组二是每组之间容器没有初始化。代码里如果用vector edges(m)那么每组循环里重新定义一次内存会自动释放这种写法比较安全。但有人喜欢提前定义全局parent、edges然后每组开头只用resize一旦忘记清空edges上一组的残余数据会混进下一组结果只能是WA。排查这类问题的方法很简单第一组数据多跑几次看看答案是不是稳定再故意构造第一个样例很大、第二个样例很小的数据如果第二个样例的答案异常那大概率就是初始化问题。还有一个输入格式分歧点有的题面写“第一行n接下来n(n-1)/2行”有的题面写“第一行n第二行m接下来m行”。这两种写法的代码区别很小但读错就全盘皆输。所以拿到任何一份代码模板第一件事不是往下看排序而是确认它假设的输入格式和你OJ上的题目格式完全一致。4.2 已经连通怎么办有一种情况容易被轻视输入的候选道路里可能本身就存在足够多、足够便宜的路甚至整个图已经连通。这时候最小生成树权值是0。并查集初始化后cnt本来就是1循环里一条边都不需要加ans保持0输出0就对了。很多同学在ans初始化这里翻车写成ans -1或没有初始化就会产生无意义的大数。我也见过另一种情况题目明确保证一定连通但你的代码在cnt变成1后仍然继续遍历后面的边而且后面的边恰好是重边导致ans被多加。虽然我在模板里写了break但还是会有人把break漏掉。漏掉break的后果是遇到平行边时最后一条小边可能会被错误地加进答案。所以提前break不是可选项是正确性的一部分。4.3 自环、平行边与数据范围自环在Kruskal里不会造成问题find两个端点结果相同直接跳过。平行边也无所谓因为排序后更小的边会先被使用另一条同端点的边在尝试加入时必然成环而被跳过。但如果你改用邻接矩阵的Prim平行边就要保留最小值否则可能被大边覆盖掉小边导致答案偏大。数据范围方面候选边数量是n(n-1)/2n在几百到一千时边权和几乎不可能超过32位int能表示的范围。但严谨起见我在工程代码里更习惯用long long存答案反正差不了几个字节但能省掉一担心。4.4 并查集写挂的表现与快速自检我见过不少次“样例过了、提交WA”的情况最后定位到并查集。症状通常是这样小数据一切正常数据稍微多一点就开始超时或结果乱七八糟。常见的并查集错误有三类find没有做路径压缩或者压缩写错导致每次查询都要遍历很长一条链unite里只改了一个点的parent没有把整个分量的根接过去初始化时循环从0开始但顶点编号从1开始导致顶点1永远游离在系统外。自检方法很简单随便构造一个只有一条边的小样例比如n2两个点之间成本5期望输出5。如果连这种都错那一定是初始化或读取问题如果对了再构造三个点、三条边、其中一条会成环的场景手算一遍期望值再提交。送上一张排查速查表我每次WA后都会按这个顺序过一遍现象最可能原因处理本地样例AC提交WA多组数据容器残留每组重新定义容器输出莫名其妙是0边没读进去或初始化错误检查读边循环和ans初值超时find无路径压缩压缩并查集答案偏大排序方向反了检查比较器方向答案偏小提前break条件写错检查cnt判断5. 从这道题出发后续变体与真实工程场景5.1 继续畅通工程已建成的道路怎么处理“畅通工程”系列后面还有“继续畅通工程”。它的输入会告诉你哪些路已经修好哪些路还在候选列表里。处理方式有两种要么在读入时把“已建好”的路的权值直接当成0再交给Kruskal要么在跑Kruskal之前先把这些路全部unite进去再把候选边排序。两种写法都正确我更喜欢第二种因为它把“已经存在的连通关系”前置了后面的主循环仍然保持“不选成环边”的语义。这里顺带说一个技巧如果题目给了“已有路径”的边但并没有把这些边的成本放到输入里那你需要在并查集初始化后立刻统一合并它们再计算剩余成本。这个操作本身不改变Kruskal的正确性反而可以省掉一堆特判。我在做这类变体题时通常先画出“哪些点已经属于同一块”然后才跑排序加边思路会清楚很多。5.2 Kruskal和Prim现场怎么选面试或做工程时我一般按这个原则选图的边数如果接近顶点数的几倍优先Kruskal如果是一个比较满的稠密图、顶点数又不大用朴素Prim写起来更快如果顶点多、边也很多就用堆优化的Prim或者继续用Kruskal看数据量。给一个实际例子你手头有100个路由器任意两台之间都可能拉专线每条专线月租不同问选哪些专线使所有路由器连通且月租最低。100个点是稠密图邻接矩阵Prim很好写但如果网络只有几十条候选线路Kruskal的“把线路按价格排序一点点连”更直观也更容易跟业务同事解释。5.3 还想再进一步的方向如果这道题你已经能一遍AC建议继续往这几个方向走两步次小生成树在最小生成树基础上替换一条边得到成本第二小的生成树严格次小生成树处理边权相等的情况坑很多最小生成树计数给定图统计有多少棵不同的最小生成树用到Matrix-Tree定理和并查集缩点瓶颈生成树找一棵生成树使最大边权最小。它与最小生成树之间有一个很有趣的关系证明方法就是Kruskal。这些方向在算法竞赛、面试题、甚至真实网络规划里都能见到影子。拿“瓶颈生成树”举例它和Kruskal的联系特别紧密Kruskal把边排序后加边第一次让图连通的那条边正好就是瓶颈生成树的最小可能最大边权。理解了这个点以后再遇到“最小化最大边权”的问题思路会顺很多。最后说点个人经验。我第一次做“还是畅通工程”的时候其实还没学过最小生成树的术语只是凭直觉觉得“先把便宜的路修了能修就修不能修就跳过”写完居然就能过测试点。后来老师上课才告诉我那个直觉就是Kruskal。所以我一直觉得这类题最核心的价值不在背代码而在于让你自己体会到“为什么排序加并查集能解决看似很复杂的选路问题”。如果你现在正卡在这道题上我的建议是先别看题解拿小规模数据自己推一遍贪心过程再把代码写出来如果WA就写一个暴力枚举所有边集合并判连通的程序在小数据上对拍很快就能定位是排序、并查集还是读入的问题。这个方法比我当年对着屏幕发呆高效太多。