最近刷题又碰到了 POJ 1251 Jungle Roads 这道题当年刚入门算法时就栽在它的输入格式上现在回头看它其实是讲清楚最小生成树MST最合适的入门题之一。题目本身不绕弯一堆写着字母的村庄若干条带维护费用的路要求用最少的费用把所有村庄连通。这不就是把所有点用最小权值的边连成一棵树的问题么Kruskal 和 Prim 两种最小生成树算法都能解决它。而这题的经典程度在于它几乎就是一个裸 MST只要吃透题意剩下的就是两种算法基本功的较量。这篇文章我会从题目建模、输入解析、Kruskal 完整实现、Prim 完整实现、两种算法对比选型、实战排坑六个方面展开所有代码都是可直接提交到 OJ 的版本我也会把当年踩过的坑和验证技巧一并交代清楚。无论是刚开始学图论的新手还是准备复习 MST 的老手这篇都应该能给你一点新东西。1. 题目到底在讲什么一眼认出最小生成树1.1 题意提炼当村长要修路题目给了一堆村庄每个村庄用一个大写字母表示村庄之间已经有若干条现成的路但每条路每年都需要维护费。作为一村之长你不可能把所有路都维护一遍那太费钱了。你的任务是选出一些路保证任意两个村庄都能通过这些路互相到达同时让总维护费用最小。把这句话翻译成图论语言村庄是顶点路是带权无向边维护费用是边权。我们要在图中选出一个子集让 n 个点全部连通并且边的总权值最小。这不就是最小生成树Minimum Spanning Tree吗一个连通图要覆盖 n 个点且总边权最小选出来的边一定构成一棵树。为什么只要选出来的边能让 n 个点连通就必然至少有 n-1 条边如果某个选边方案里存在环去掉环上一条边还能保持连通而且总权值只会更小。所以最优解一定是无环的这就是一棵生成树。1.2 图论建模把村庄变成点把路变成边读题之后第一件事就是在草稿纸上建图。题目输入保证 n 最大只有 26也就是 A 到 Z 全上场也就 26 个点边数最多是 n*(n-1)/2 325 条。这是一个非常小的稠密图。建模方式有两种对应两种算法的数据载体边集数组把所有边按起点、终点、权值存进数组Kruskal 用。邻接矩阵用 mp[i][j] 记录点 i 到点 j 的直接边权Prim 的朴素写法用。这两种结构我后面都会给出完整的构建设计。先说结论因为 n 极小邻接矩阵开 30×30 就够了边集数组开 400 条也绰绰有余完全不需要担心空间。1.3 为什么不是最短路径别把 MST 和最短路搞混初学者最容易犯的错误是一看到费用最小就想到 Dijkstra。但注意题目要求的是任意两个村庄都能通过选出的路互相到达不是求从 A 村到某村的最短路径。这两者的差异很微妙但很关键。最短路径关心的是从指定起点到终点的一条路可能只覆盖途经的几个点最小生成树关心的是让整张图连通的最小成本骨架它不关心你从 A 怎么走到 B只关心全图是否连通。更直白地说MST 是给整张图做全局连通预算最短路是给两个点做单点通行方案。看到能否互相到达 总费用最小这个组合直接锁定 MST不要犹豫。2. 输入解析的坑与图的构建2.1 这个输入格式骗了多少人很多人第一次做这题不是卡在算法上而是卡在读入上。输入是多组数据每一组是这样组织的第一行一个整数 n表示村庄数量n0 表示所有测试结束。 接下来 n-1 行每行以一个大写字母开头后面跟一个整数 k表示从这个村庄出发有 k 条路然后跟着 k 组大写字母 整数分别表示路的另一端和维护费用。样例长这样9 A 2 B 12 I 25 B 3 C 10 H 40 I 8 C 2 D 18 G 55 D 1 E 44 E 2 F 60 G 38 F 0 G 1 H 35 H 1 I 35 3 A 2 B 10 C 40 B 1 C 20 0注意两点第一为什么是 n-1 行而不是 n 行因为每行代表一个字母开头的顶点最后一个字母比如第一组的 I 或第二组的 C没有比它更大的邻接点了所以省略。第二每条路只会出现一次比如 A 下面写了 B 12B 那一行就不会再写 A 12。这意味着输入本身就是一个上三角形状的邻接表不用考虑重边去重的问题。2.2 用 scanf 优雅地跳过空白字符这里最经典的坑是%c 会读入空格和换行符。如果你直接 scanf(%c %d, ch, k)读到的很可能是一个换行符程序直接乱掉。正确做法是让 %c 前面带一个空格scanf( %c %d, ch, k)。这个前导空格会告诉 scanf 跳过所有空白字符直接定位到真正的字母。这是一种轻量又干净的写法比调用 getchar() 手动吃换行要可靠得多。scanf( %c, u); scanf( %c %d, v, w);如果你用的是 cincin ch 天然会跳过空白不需要额外处理。但 OJ 上 scanf 通常更快后面所有代码我统一用 scanf 写。2.3 字母坐标转数字下标村庄用大写字母表示需要换算成数组下标通用做法是 ch - A。A 对应 0B 对应 1Z 对应 25。建图时我通常会同时维护邻接矩阵和边集数组为的是同一道题在本地就能把 Kruskal 和 Prim 都跑一遍互相验证const int MAXN 30; const int INF 0x3f3f3f3f; int mp[MAXN][MAXN]; int m; // 边数 struct Edge { int u, v, w; } edges[MAXN * MAXN];读入时int n; while (scanf(%d, n) 1 n) { memset(mp, 0x3f, sizeof(mp)); m 0; for (int i 0; i n - 1; i) { char u; int k; scanf( %c %d, u, k); while (k--) { char v; int w; scanf( %c %d, v, w); int a u - A, b v - A; // 邻接矩阵写最小权值防重边 mp[a][b] mp[b][a] min(mp[a][b], w); // 边集数组直接存Kruskal 用 edges[m] {a, b, w}; } } // ... 算法部分 }这里有个细节读入的 u 和 v 都是 char直接用 char 参与运算之前必须转成 int。忘了 - A 的后果就是数组越界访问OJ 上表现很可能是 Runtime Error 或者乱输出。提示mp 初始化成 INF 用的是 memset(mp, 0x3f, sizeof(mp))0x3f3f3f3f 是竞赛里常用的无穷大惯例两个这样的值相加也不会溢出 int安全。3. Kruskal 算法并查集 边贪心3.1 Kruskal 的核心逻辑与正确性直觉Kruskal 的思路极其朴素把所有边按权值从小到大排序然后一条条看如果这条边连接的两个点目前不在同一个连通块里就选它如果已经在同一个连通块里说明加上这条边会形成环丢弃。这个过程很像搭桥一开始每个村庄都是孤岛你把所有可能的桥按造价从低到高排好从最便宜的开始搭每次搭一座桥连接两个尚未连通的岛屿直到所有岛屿变成一个整体。桥的总造价必然最低因为你永远优先选择当前最便宜且能产生价值连通两个不同块的桥。为什么贪心不会错直观理解是如果某条权值最小的可行边不选它那么最终生成树里从这两个连通块之间取替它的一定是另一条权值更大或相等的边总权值不可能更小。更严格的证明涉及切割性质这里不展开但做题时接受这个结论就行。3.2 并查集路径压缩与合并细节Kruskal 的配套数据结构是并查集用来快速判断两个点是否在同一连通块。并查集的三个核心操作初始化每个点独立fa[i] i。查找find(x) 返回 x 所在集合的根路径压缩让树更扁平。合并把两个集合的根连起来。路径压缩的 find 写法很固定int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); }关于合并简单起见可以直接 fa[fx] fy效果没问题。你要是追求最优可以加按秩合并rank但对于 n 26 的点数秩优化带来的收益可以忽略别把代码搞复杂。判断边 u-v 是否成环int fu find(u); int fv find(v); if (fu ! fv) { fa[fu] fv; // 两个集合合并 ans w; cnt; // 选边计数 }注意所有边的读入结束后要先排序再遍历。排序结构体时重载小于号即可。3.3 完整 Kruskal 实现#include cstdio #include algorithm using namespace std; const int MAXN 30; struct Edge { int u, v, w; bool operator(const Edge other) const { return w other.w; } }; Edge edges[MAXN * MAXN]; int fa[MAXN]; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } int main() { int n; while (scanf(%d, n) 1 n) { int m 0; for (int i 0; i n - 1; i) { char u; int k; scanf( %c %d, u, k); while (k--) { char v; int w; scanf( %c %d, v, w); edges[m].u u - A; edges[m].v v - A; edges[m].w w; } } sort(edges, edges m); for (int i 0; i n; i) fa[i] i; int ans 0, cnt 0; for (int i 0; i m cnt n - 1; i) { int fu find(edges[i].u); int fv find(edges[i].v); if (fu ! fv) { fa[fu] fv; ans edges[i].w; cnt; } } // 如果 cnt n-1说明图不连通但这题保证连通 printf(%d\n, ans); } return 0; }这段代码可以直接交。重点看两处排序后循环里对 cnt 做了提前终止优化这是小优化但养成习惯是好的find 路径压缩是递归写法n 很小不用担心栈溢出。Kruskal 的时间复杂度主要花在排序上O(m log m)m 是边数。本题 m 最大也就 325排序成本几乎可以忽略。4. Prim 算法点贪心 松弛数组4.1 Prim 的核心逻辑与 dist 数组设计Prim 的思路和 Kruskal 完全不同它从一个点出发每次向外扩展一个点每次选择的依据是当前已经选中的点集合到未被选中的点集合之间哪条边的权值最小。这种思路的直观场景是修电网从村口开始通电通电范围每扩大一次就找一个离通电区域最近的还没通电的村庄拉线进去直到所有村庄通电。每次拉线都是当前最优的向外连接所以总成本最低。Prim 的核心是一个 dist 数组dist[v] 表示当前已选集合到顶点 v 的最小边权值。每轮从未选点中挑出 dist 最小的点 u把它加入集合。然后尝试用 u 的所有邻边更新其他未选点的 dist。dist 数组和 Dijkstra 里的 dist 长得像但含义完全不同Dijkstra 的 dist 是到起点的最短距离Prim 的 dist 是到已选集合的最小连接代价。这点一定要区分清楚否则会写出假 Prim。4.2 朴素 Prim 的完整实现因为 n 26直接写 O(n^2) 的朴素 Prim 就够了不需要堆优化。堆优化 Prim 适合稀疏图这里的图是接近完全的稠密图n^2 本身就是最优复杂度。#include cstdio #include cstring #include algorithm using namespace std; const int MAXN 30; const int INF 0x3f3f3f3f; int mp[MAXN][MAXN]; int dist[MAXN]; bool vis[MAXN]; int main() { int n; while (scanf(%d, n) 1 n) { memset(mp, 0x3f, sizeof(mp)); for (int i 0; i n - 1; i) { char u; int k; scanf( %c %d, u, k); while (k--) { char v; int w; scanf( %c %d, v, w); int a u - A, b v - A; mp[a][b] mp[b][a] min(mp[a][b], w); } } memset(dist, 0x3f, sizeof(dist)); memset(vis, 0, sizeof(vis)); // 从 0 号点A 村开始 dist[0] 0; int ans 0; for (int i 0; i n; i) { int u -1, minDist INF; for (int v 0; v n; v) { if (!vis[v] dist[v] minDist) { minDist dist[v]; u v; } } if (u -1) break; // 图不连通防止死循环 vis[u] true; ans minDist; for (int v 0; v n; v) { if (!vis[v] mp[u][v] dist[v]) { dist[v] mp[u][v]; } } } printf(%d\n, ans); } return 0; }几个容易写错的地方其一更新 dist 的时候一定只更新未访问点。如果已访问点被更新后续可能会重复把点加入答案费用重复计算。其二ans minDist 而不是 ans dist[u]其实 minDist 就是 dist[u]写哪个都行我习惯直接拿 minDist 加少一次数组访问。其三图不连通时 u 会保持 -1必然要 break否则下面 mp[u][v] 访问到 mp[-1][v] 直接越界崩溃。本题保证输入连通但防御性编程不能丢。Prim 朴素写法的时间复杂度是 O(n^2)因为它有两层 n 循环每轮遍历找最小 dist 是 O(n)一共 n 轮更新也是 O(n)总共 O(n^2)。在 n26 时这就是眨眼完成连常数复杂度都可以忽略。5. 两种算法对比与选型参考5.1 复杂度、适用场景与编码难度对照对比维度KruskalPrim朴素核心数据结构边集数组 并查集邻接矩阵 dist 数组时间复杂度O(m log m)O(n^2)空间复杂度O(m)O(n^2)更适合的图稀疏图稠密图 / 完全图编码难点排序 并查集查环初始化 dist 每轮更新是否依赖起点不依赖所有边统一处理需要指定一个起点重边处理多条边排序后天然取最小存矩阵时取 min从这张表能看出一个规律Kruskal 的复杂度只和边数 m 相关和点数 n 关系不大Prim 只和点数 n 相关和边数 m 无关。稀疏图边少Kruskal 划算稠密图边多到接近 n^2 时Prim 的 n^2 更稳定。5.2 这道题两种算法都轻松秒杀POJ 1251 的数据范围是 n 26边数最多 325。这个规模下你随便用哪种算法时间都约等于 0真正的考察点其实是你能不能写出正确逻辑而不是优化。我的建议是这道题一定要把两种算法都写一遍。理由很实在Kruskal 的并查集是很多图论算法的基础值得反复手写。Prim 的 dist 数组更新和 Dijkstra 长得像练一遍能帮你把两者彻底区分开。两套代码互相跑同一组样例答案能对拍比任何调试都安心。5.3 个人选型的碎碎念刷题和做工程不一样刷题追求学过就会用。我个人在遇到 MST 时优先级是能一眼构建出边集的就用 Kruskal因为不需要额外的邻接矩阵心里少一层负担如果图是以邻接矩阵形式给出的直接用 Prim省去把矩阵转成边集的一堆循环。这道题的输入格式天然就是一个上三角邻接表转边集很直接所以我更推荐初学者这道题先写 Kruskal逻辑链条最短排序、查环、合并三步走完。6. 实战排坑与经验总结6.1 scanf 读字符的换行坑前面提到过scanf(%c) 不会跳过空白。要是某天你写了scanf(%c %d, u, k);大概率 u 读到的是上一行末尾的换行符k 读到的变成下一个字母的 ASCII 值整个输入全乱。正确写法是前面加空格scanf( %c %d, u, k)。这个空格可以出现在格式串的最前面也可以紧跟在其他占位符之后。我建议形成肌肉记忆只要用 %c前面必须补空格不要存侥幸心理。注意如果用了 cincin 会自动跳过空白不需要也不能加多余空格混用 cin 和 scanf 时要小心。6.2 多组测试数据的初始化陷阱这题是多组数据最阴险的问题就是数组没清干净。尤其注意三件事mp 数组要重新 memset 成 INF否则上一组残留的边权会被当成新图的边。fa 数组要重新初始化因为并查集的操作会让根节点不断变化不能用上一次的结果。dist 和 vis 在 Prim 里也必须重置。一个实用的调试技巧把每组数据的 n 和边数打印出来看看和输入是否对得上。如果第二组数据 n3 却跑出 30 条边多半就是没清干净。6.3 重边与自环的处理这道题输入保证每条边只出现一次正常不会遇到重边。但如果你用邻接矩阵存图碰到其他题目出现重边时一定要在存矩阵时取最小值mp[a][b] mp[b][a] min(mp[a][b], w);如果直接赋值重边里权值较大的那条会覆盖小的导致答案变大。边集数组则不用太担心重边Kruskal 排序后自然先用最小那条但自环还是要小心好在题目保证不会有。6.4 用两组代码对拍验证我第一次做这题时写完 Kruskal 提交是 Accepted但还是有点心虚于是又写了一遍 Prim拿样例输入直接跑两边输出完全一致。从那以后我就养成了同一道题用两种算法互相验证的习惯特别是 MST 这种结论性很强的算法题。对拍时要注意如果答案不一样先别急着怀疑算法先用笔算小样例确认是取错边还是更新错了 dist。样例第一组的答案我记得是 216第二组 n3 的结果是 30你可以拿这个结果验证自己代码。6.5 关于 EOF 读入的细节多组数据的读入标准姿势while (scanf(%d, n) 1 n) { ... }scanf 的返回值是成功读入的变量个数。文件结束时返回 EOF也就是 -1所以 1 表示成功读入一个 n然后再判断 n 是否为 0。两个条件叠加既不会死循环也不会把最后的 0 当成一组数据处理。如果你漏掉 1 只写 n在数据末尾时 scanf 返回 EOFEOF 不为 0循环可能继续执行然后 n 是一个残留值直接出锅。这个细节构成的 bug 特别隐蔽我亲眼见过身边人查了半小时。6.6 防御性检查 cnt 和树的连通性Kruskal 选边结束后理想情况下 cnt 应该等于 n-1。如果图不连通cnt 会小于 n-1ans 也不是一个合法生成树的权值。我建议代码里顺手加一个判断// 如果 cnt ! n - 1说明图不连通 // 这道题保证连通所以可以不处理但加上更稳这类防御性代码在竞赛里不扣分反而能帮你在样例刁钻的时候快速定位问题来源。结尾一个建议留给后来的刷题人我个人做完这道题最大的收获不是背下来了 Kruskal 和 Prim 的模板而是理解了算法是为数据结构服务的这句话。Kruskal 的边集排序 并查集的组合和 Prim 的邻接矩阵 dist 数组组合本身就是在不同的数据组织方式下做出的自然选择。最后再分享一个小技巧如果你刚开始学 MST把这道题当作对拍练习来做——左手写 Kruskal右手写 Prim两边跑同一份输入再故意改错其中一行比如把并查集合并方向反掉、把 dist 更新条件写成 mp[u][v] dist[u]观察答案怎么变化。这种主动制造 bug的练习法比连续刷十道同类题都更能帮你记住算法的边界和细节。Jungle Roads 题目不大数据温柔正是做这种实验的完美试验场。