最近刷题又碰到了 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，表示村庄数量，n=0 表示所有测试结束。 接下来 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 12，B 那一行就不会再写 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);

如果你用的是 cin，cin >> ch 天然会跳过空白，不需要额外处理。但 OJ 上 scanf 通常更快，后面所有代码我统一用 scanf 写。

2.3 字母坐标转数字下标

村庄用大写字母表示，需要换算成数组下标，通用做法是 ch - 'A'。A 对应 0，B 对应 1，Z 对应 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)。在 n=26 时这就是"眨眼完成"，连常数复杂度都可以忽略。

5. 两种算法对比与选型参考

5.1 复杂度、适用场景与编码难度对照

从这张表能看出一个规律：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，前面必须补空格，不要存侥幸心理。

注意：如果用了 cin，cin >> 会自动跳过空白，不需要也不能加多余空格，混用 cin 和 scanf 时要小心。

6.2 多组测试数据的初始化陷阱

这题是多组数据，最阴险的问题就是数组没清干净。尤其注意三件事：

• mp 数组要重新 memset 成 INF，否则上一组残留的边权会被当成新图的边。
• fa 数组要重新初始化，因为并查集的操作会让根节点不断变化，不能用上一次的结果。
• dist 和 vis 在 Prim 里也必须重置。

一个实用的调试技巧：把每组数据的 n 和边数打印出来，看看和输入是否对得上。如果第二组数据 n=3 却跑出 30 条边，多半就是没清干净。

6.3 重边与自环的处理

这道题输入保证每条边只出现一次，正常不会遇到重边。但如果你用邻接矩阵存图，碰到其他题目出现重边时，一定要在存矩阵时取最小值：

mp[a][b] = mp[b][a] = min(mp[a][b], w);

如果直接赋值，重边里权值较大的那条会覆盖小的，导致答案变大。边集数组则不用太担心重边，Kruskal 排序后自然先用最小那条；但自环还是要小心，好在题目保证不会有。

6.4 用两组代码对拍验证

我第一次做这题时，写完 Kruskal 提交是 Accepted，但还是有点心虚，于是又写了一遍 Prim，拿样例输入直接跑，两边输出完全一致。从那以后我就养成了"同一道题用两种算法互相验证"的习惯，特别是 MST 这种结论性很强的算法题。

对拍时要注意：如果答案不一样，先别急着怀疑算法，先用笔算小样例，确认是取错边还是更新错了 dist。样例第一组的答案我记得是 216，第二组 n=3 的结果是 30，你可以拿这个结果验证自己代码。

6.5 关于 EOF 读入的细节

多组数据的读入标准姿势：

while (scanf("%d", &n) == 1 && n) { ... }

scanf 的返回值是成功读入的变量个数。文件结束时返回 EOF（也就是 -1），所以 == 1 表示成功读入一个 n；然后再判断 n 是否为 0。两个条件叠加，既不会死循环，也不会把最后的 0 当成一组数据处理。

如果你漏掉 == 1 只写 && n，在数据末尾时 scanf 返回 EOF，EOF 不为 0，循环可能继续执行，然后 n 是一个残留值，直接出锅。这个细节构成的 bug 特别隐蔽，我亲眼见过身边人查了半小时。

6.6 防御性检查 cnt 和树的连通性

Kruskal 选边结束后，理想情况下 cnt 应该等于 n-1。如果图不连通，cnt 会小于 n-1，ans 也不是一个合法生成树的权值。

我建议代码里顺手加一个判断：

// 如果 cnt != n - 1，说明图不连通 // 这道题保证连通，所以可以不处理，但加上更稳

这类防御性代码在竞赛里不扣分，反而能帮你在样例刁钻的时候快速定位问题来源。

结尾：一个建议留给后来的刷题人

我个人做完这道题最大的收获不是背下来了 Kruskal 和 Prim 的模板，而是理解了"算法是为数据结构服务的"这句话。Kruskal 的边集排序 + 并查集的组合，和 Prim 的邻接矩阵 + dist 数组组合，本身就是在不同的数据组织方式下做出的自然选择。

最后再分享一个小技巧：如果你刚开始学 MST，把这道题当作"对拍练习"来做——左手写 Kruskal，右手写 Prim，两边跑同一份输入，再故意改错其中一行（比如把并查集合并方向反掉、把 dist 更新条件写成 mp[u][v] < dist[u]），观察答案怎么变化。这种"主动制造 bug"的练习法，比连续刷十道同类题都更能帮你记住算法的边界和细节。Jungle Roads 题目不大，数据温柔，正是做这种实验的完美试验场。