P1348公交网建设：最小生成树Prim与Kruskal算法深度解析

1. 题目拆解：公交网建设到底在考什么

P1348这道题，乍一看是城市公交网建设，好像是个规划问题，但剥开外壳就是一道非常典型的**最小生成树（MST）**问题。这类题目在信息学奥赛里属于"模板题中的变式"，也就是说，算法本身不难，难在你能否在考场紧张状态下，一眼看穿它要干什么，然后快速选择正确的算法实现。

题目大概是这样：某城市调查了市民的出行需求，打算在若干站点之间修建公交线路，每条候选线路都有对应的建设费用。要求是让任意两个站点之间都能通过已经建设的线路互相到达，同时总建设费用尽可能低。也就是说，给你一张带权无向图，顶点是站点，边是候选线路，边权是建设费用，你要挑出一部分边，让整个图连通，并且总边权最小——这就是最小生成树的标准定义。

这里有个关键点，题目不一定只让你求最小费用总和，它有可能要求你输出具体选中的线路，也有可能只是一个裸求权值的题目。我当年做题时总结了一个经验：看到"任意两个点之间互相到达""总费用最小"这类关键词，直接往 MST 方向想；看到"修建若干条路/公交线/管道/网线"加上"使所有点连通"的描述，99%是最小生成树。

2. 两种经典算法，为什么P1348两者都可以

最小生成树有两种实现思路：Prim算法和Kruskal算法。P1348这类题目其实并不限定你必须用哪种，两种都能过，但选错思路可能导致代码量膨胀或者难调试，所以我还是要把它们的原理和适用场景讲透。

2.1 Prim算法：从点出发，逐点"长"出生成树

Prim算法的核心思想就像栽树：从任意一个起点开始，把这棵树看成一个集合，每次从这个集合到集合外找一个边权最小的边，把对应的新点拉进集合，重复 n-1 次，就得到一棵最小生成树。

它的朴素写法是两层循环，复杂度 O(n²)，不管边有多少，复杂度都稳定。所以当题目给出的图比较"密"（边数接近 n² 级别）时，Prim 优先。比如 n=1000，边数好几万甚至十几万，用 Kruskal 排序都要吃不少时间，Prim 的 n² 反而稳。

实现上 Prim 需要维护一个 lowcost 数组，记录当前集合外每个点到集合内某个点的最小边权。每次扫描 lowcost 找最小值，找到后加入集合，再更新 lowcost。这个逻辑和 Dijkstra 非常像，区别只在于 Dijkstra 维护的是从源点到各点的最短路径，Prim 维护的是集合到各点的最小边权。很多初学者会把这两个搞混，我建议用一个笨办法区分：Dijkstra 有起点和目标点，Prim 只在乎"已经连成一片的区域"扩张到哪里。

2.2 Kruskal算法：排序边，用并查集连点成树

Kruskal 的思路更直接：把所有的边按权值从小到大排序，然后一条一条尝试加入生成树。加入的条件是这条边的两个端点当前不在同一个连通块里——也就是用并查集判断。如果会形成环，就跳过这条边。直到加入了 n-1 条边为止。

它的复杂度主要消耗在排序上，O(m log m)，m 是边数。所以对于边数相对较少的"稀疏图"，Kruskal 是更好的选择。

P1348的数据范围，我记忆中是站点数 n 和候选线路数 m 都不会太大，两种算法都能过。但我自己写这道题的时候更习惯用 Kruskal，原因有三个：第一，它不需要考虑起点取哪个点；第二，并查集的板子写起来熟，不容易出边界问题；第三，题目如果要求输出选了哪些线路，Kruskal 自然地在选边时就把边记录下来了，而 Prim 还需要额外存每条边是连接哪两个点的，稍麻烦一点。

2.3 模板代码对比表

3. 完整代码实现与逐段解析

既然两种算法都能解 P1348，我就把两个版本的代码都放出来，并解释每一段在干什么、有什么坑。

3.1 Kruskal版本（推荐）

#include <iostream> #include <algorithm> using namespace std; struct Edge { int u, v, w; } edges[10005]; // 根据题目数据范围调整 int fa[105]; // 并查集数组，n 一般不超过 100 int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } bool cmp(Edge a, Edge b) { return a.w < b.w; } int main() { int n, m; cin >> n >> m; // 输入站点数与候选线路数 for (int i = 1; i <= n; i++) fa[i] = i; // 并查集初始化 for (int i = 1; i <= m; i++) { cin >> edges[i].u >> edges[i].v >> edges[i].w; } sort(edges + 1, edges + m + 1, cmp); // 按权值从小到大排序 int ans = 0, cnt = 0; for (int i = 1; i <= m; i++) { int fu = find(edges[i].u); int fv = find(edges[i].v); if (fu != fv) { // 不在同一个连通块，说明这条边可以选 fa[fu] = fv; ans += edges[i].w; cnt++; if (cnt == n - 1) break; // 已经连成树，提前退出 } } if (cnt == n - 1) cout << ans << endl; else cout << "无法连通" << endl; // 题目若非保证连通，需要这个判断 return 0; }

这里有几个细节很值得说：

并查集的路径压缩：find 函数里fa[x] == x ? x : fa[x] = find(fa[x])这行，同时做了路径压缩。第一次写并查集的时候，漏掉路径压缩也能过小数据，但遇到 n=1000 甚至更大时，没有路径压缩的并查集在找祖先时可能一层一层往上爬，最坏退化成链，复杂度从近乎 O(1) 变成 O(n)，整个程序就慢下来了。所以压缩不能省。

提前 break 的条件：cnt 记录已选边数量。最小生成树只要 n-1 条边就够把所有点连起来，选够了直接退出循环，不用再遍历剩余边。如果你不 break，结果也不会错，但浪费了时间。更重要的是，如果你最后统计出来 cnt 不等于 n-1，说明图本身不连通，题目如果没保证一定有解，这一步判断就派上用场了。

3.2 Prim版本

#include <iostream> #include <cstring> using namespace std; const int INF = 0x3f3f3f3f; int n, m; int G[105][105]; // 邻接矩阵存图 int lowcost[105]; bool vis[105]; int prim() { memset(lowcost, 0x3f, sizeof(lowcost)); memset(vis, false, sizeof(vis)); lowcost[1] = 0; // 从 1 号站点开始 int ans = 0; for (int k = 1; k <= n; k++) { int u = -1; for (int i = 1; i <= n; i++) { if (!vis[i] && (u == -1 || lowcost[i] < lowcost[u])) { u = i; // 找集合外 lowcost 最小的点 } } if (u == -1) return -1; // 图不连通 vis[u] = true; ans += lowcost[u]; for (int v = 1; v <= n; v++) { if (!vis[v] && G[u][v] < lowcost[v]) { lowcost[v] = G[u][v]; // 更新 lowcost } } } return ans; } int main() { cin >> n >> m; memset(G, 0x3f, sizeof(G)); // 初始化邻接矩阵全部为 INF for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; G[u][v] = G[v][u] = min(G[u][v], w); // 可能存在重边，取最小值 } int ans = prim(); cout << ans << endl; return 0; }

Prim 版本有四个容易踩的坑：

• 邻接矩阵初始化必须用 INF，不能默认为 0，否则更新 lowcost 时全部变成 0，结果直接错。
• 输入时如果出现重边（两个站点之间给出了多条不同的候选线路），必须保留权值最小的那条，否则G[u][v] = w的写法会把小权值覆盖掉。
• memset(G, 0x3f, sizeof(G))会把每个字节都设成 0x3f，也就是 int 的 0x3f3f3f3f，这是竞赛里常用的 INF 技巧。注意如果用memset(vis, false, sizeof(vis))初始化 bool 数组是没问题的。
• Prim 的 lowcost[1] 初始为 0，表示 1 号点已经在集合里了。如果题目要求输出所有选中的边，需要额外用一个 pre 数组记录每个点是经由哪条边加入集合的，输出时把 (pre[v], v, w) 打出来。

4. 手推样例：让算法跑一遍才踏实

光贴代码不够，我习惯把样例手动推一遍，这样可以验证自己对算法过程的理解是否准确。假设题目给出如下输入：

5 7 1 2 2 2 3 4 3 4 6 4 5 8 1 5 10 2 5 12 1 3 3

用 Kruskal 的过程是这样的：

排序后的边顺序为：

1. (1,2,2)
2. (1,3,3)
3. (2,3,4)
4. (3,4,6)
5. (4,5,8)
6. (1,5,10)
7. (2,5,12)

• 选 (1,2,2)，并查集连通 1 和 2。
• 选 (1,3,3)，连通 1、2、3。
• 看 (2,3,4)，发现 2 和 3 已经在同一个集合里，跳过。
• 选 (3,4,6)，连通 1、2、3、4。
• 看 (4,5,8)，连通 1、2、3、4、5，此时 cnt = 4，等于 n-1，退出。
• 总费用：2 + 3 + 6 + 8 = 19。

注意第五步虽然 (1,5,10) 的权值比 (4,5,8) 小，但排序后 (4,5,8) 排在 (1,5,10) 前面，所以先处理它恰好选中；如果 (1,5,10) 排到前面，它也会被选中。这就是 Kruskal 的特点：所有最小生成树的权值总和相同，但选出的边集合可能有多种。

用 Prim 从 1 号点出发：

• lowcost 初始 {0, 2, 3, INF, 10}（与 1 直接相连的点更新）。
• 选 2 号点，lowcost[3] 被更新为 4（但原来 3 是 3，所以不更新），lowcost[5] 被更新为 12（原来 10，不更新）。
• 选 3 号点（权值 3），lowcost[4] 更新为 6，lowcost[5] 仍为 10。
• 选 4 号点（权值 6），lowcost[5] 更新为 8。
• 选 5 号点（权值 8）。
• 总费用 0 + 2 + 3 + 6 + 8 = 19。

两条路径结果一致，这就是 MST 的性质：总权值唯一。

提示：我建议初学者拿到任何一道 MST 题，都先手动模拟一遍小样例。很多人在代码里跑不出错，但思路细节是模糊的，手动模拟一遍能把"贪心为什么能保证全局最优"这个关键给彻底理解掉。

5. 常见错误与问题排查实录

以下是我在实际做题和带人时，看到的高频问题，列成一张速查表，照着排查能省不少调试时间。

除了这张表，还有一个特别隐蔽的坑：图不连通时，Kruskal 的 cnt 达不到 n-1，但很多模板不会做判断就直接输出 ans。题目如果保证图连通，那么不影响；但如果是变种题（比如问你是否能建设，不能建设输出某个值），漏掉这个判断就是大问题。所以我会建议大家把"判断 cnt == n-1"这步保留到代码里，哪怕题目保证连通，这行代码也就是多了个 if，不会影响成绩。

还有一个工程细节：如果用 Kruskal，边的结构体数组开多大？千万不要开成 m+1 就完事，如果 m 是 10000，那么结构体数组要有 10005 的大小，多出来的几个位置是用来防止下标越界的。如果我写Edge edges[10005]，但实际 m=10000，那也没问题；但如果我写Edge edges[10000]，下标从 1 开始到 10000，刚好用满，最后一个元素的地址是 edges[10000]，并不越界，但 C++ 数组下标从 0 开始，定义一个长度为 10000 的数组，最大合法下标是 9999，下标 10000 就越界了。这个错误非常常见。

6. 延伸思考：从模板题到变种题

P1348 在教材里的定位是例题，它的价值不只是让你 AC 这一道题，而是让你通过它掌握整类 MST 问题的套路。基于这道题，有几个常见的变种方向，值得提前准备。

6.1 判断某条边是否是"必选边"

有时候题目会问，在保证总费用最小的前提下，某条候选线路是否一定会被选中。这种问题的一个思路是：先求一遍 MST 的总权值，然后强制先把这条边加入生成树，再用 Kruskal 跑剩下的边，如果加入这条边之后生成的总权值等于原 MST 的总权值，那说明存在一棵包含它的最小生成树。注意这里说的是"存在"，不是"一定被选中"。

如果需要判断"所有最小生成树都包含某边"，那就更复杂了，需要用到"次小生成树"或"替换边"的概念。大体思路是：在一棵 MST 上，如果加入一条非树边 e，会形成一个环，环上的最大权值边如果和 e 权值相等，说明这条 e 可以替换掉那条边，原 MST 就不是唯一的。把每条非树边扫一遍，就能判断出哪些边在 MST 中一定会出现。

6.2 次小生成树

P1348 如果扩展一问"在保证连通的前提下，费用的第二小方案是多少"，就需要用到次小生成树。做法是先求 MST，然后对 MST 做树链剖分或倍增 LCA，维护树上路径的最大边权。枚举每一条非树边，将其加入树中形成环，再删掉环上的最大边，得到一个新的生成树，取其中最小的权值，就是次小生成树。第二种方法是用"非树边最小差值"的思想：对所有非树边 e=(u,v,w)，找 u 到 v 路径上的最大树边 w_max，如果 w 和 w_max 的差值最小，用它替换，得到的生成树就是次小生成树。

6.3 输出方案

有些题目不只要你输出最小费用，还会要求输出具体选中的线路，甚至按某种顺序（如字典序）输出。这时候 Kruskal 就非常方便，因为你在选边的时候就是把边按顺序加入的，直接在这个循环里printf("%d %d\n", edges[i].u, edges[i].v)即可。如果用 Prim，则要额外维护 pre 数组，记录每个顶点是被哪条边拉进集合的。

6.4 负权边和负环

最小生成树题目里有时会出现负数权值。很多人第一反应是"那岂不是可以无限选边降低总费用？"，但别忘了 MST 要求选的是一棵树，边数是 n-1，你不能多加边。所以负权边对 Kruskal 和 Prim 没有任何特殊影响，照常处理即可。真正需要注意负权边的是最短路径问题（Bellman-Ford 处理负环），不要把两个模型的细节搞混。

7. 做题节奏与调试建议

最后说说考场上的时间分配和调试策略。信息学奥赛的题，时间紧任务重，一道模板题必须在 15 到 20 分钟内写完并验证完毕，不然后面的大题会吃亏。

我个人的节奏是这样的：

• 读题 1 分钟，圈出关键点：站点数是 n，候选线路数是 m，费用是边权，要求是连通且总费用最小。
• 判断算法 10 秒：连通+最小费用，直接 MST。
• 决定用哪种实现 30 秒：看数据范围，m 大用 Prim，m 小用 Kruskal。题目如果没有给数据范围，默认用 Kruskal，因为并查集板子更短，手写出错率低。
• 写代码 5 到 8 分钟：把板子默写出来，注意数组大小、并查集初始化、重边处理。
• 造数据测试 3 分钟：先用题目的样例，再自己造一个 1 个点、2 个点、3 个点的边界数据，检查连通性和输出格式。
• 最后检查 2 分钟：重点看数组开够没有，是否存在图不连通的情况，输出是否要换行。

调试时有一个技巧：如果答案不对劲，不要急着打一堆 printf。先在纸上画出样例图，手动跑一遍 Kruskal 或 Prim，对照代码逻辑，看是哪个 if 判断多了或少了。我有一次在 Prim 的 lowcost 更新那里写成了lowcost[v] = G[u][v]而不是min(lowcost[v], G[u][v])，结果所有点的 lowcost 都被新边覆盖，答案完全错乱。这种逻辑错误靠单步调试很难发现，但手推一遍立刻暴露。

还有一个隐蔽的考场习惯问题：输出格式。题目可能要求每个方案换行输出，也可能只要最终费用。用cout << cnt << endl和cout << cnt << '\n'在常规判题中差别不大，但如果你用printf("%d\n", ans)时漏了\n，在某些判题系统上是会被判格式错误的。所以无论多简单的题，输出前都检查一遍换行。

另外提醒一个 C++ 细节：comp 函数如果写成return a.w <= b.w（带等号），在 sort 里不会立刻出错，但某些 STL 实现里，严格的弱排序要求比较函数不能对相等的元素返回 true，否则排序行为是未定义的。所以一律写<，不要写<=。这种 bug 在数据大了之后才显现，排查起来非常头疼。

8. 我对这道题价值的重新思考

把 P1348 当作例题反复做，会不会觉得太基础没必要？我当年也有这种想法，但后来参加过一次省赛被一道翻车题教训后，反而回过头把教材模板题又刷了两遍。MST 看起来简单，但它是后续许多高级算法的跳板。

P1348 的建模思维非常重要：把一个实际生活场景（公交网建设）抽象成图论模型，这个过程本身就是 OI/ACM 的核心能力。很多时候题目难不在算法本身，而在你能不能把现实问题转成已知模型。公交线路、通信布线、水管铺设、电网设计，这些都可以是 MST 的皮，但考的本质从来不换。我建议刷完 P1348 后，拿其他平台的同等难度的题练手，比如最小生成树的裸题、判断连通性的应用题、需要输出方案的实现题，每一步都确保自己从"看懂"到"闭眼能写"。

另外，如果你是一个算法竞赛的新手，千万不要只满足于 AC。尝试把代码改写几个版本：比如用优先队列优化一下 Prim，或者给 Kruskal 加上输出方案的功能。这种"改动"训练，比单纯刷新题更能让你吃透代码结构。我在学了堆优化 Prim 后，对二叉堆、结构体排序比较函数的理解都上了一个台阶，这些在后续最短路、状态压缩题里都用得上。

说到底，例题就是一个锚点。它帮你把"最小生成树"这个知识锚在脑子里，以后遇到类似的题，你不需要从零推导，直接回忆 P1348 的思路和代码，然后微调试应变化。信息学奥赛考到后期，很多题表面上千变万化，骨子里跑的还是模板算法的组合与变体。把这道题吃透，就等于给整类题打好了地基。