洛谷P3366这道模板题我当年第一次认真做它的时候Kruskal 和 Prim 各写了一遍结果第一遍全 WA。原因不是算法背错了而是“不连通输出 orz”这个细节被我当成了摆设。后来在蓝桥杯省赛和 ACM 训练里最小生成树相关题目反复出现我才意识到这题为什么是“必刷”——它不是让你背模板而是逼你理解两种贪心策略各自的适用边界。这篇文章就把我对最小生成树、Kruskal、Prim 的理解连同 P3366 的完整解法和选型经验一次性说清楚适合准备蓝桥杯 C/C、Java、Python 组的选手也适合 ACM 入门阶段想系统过一遍图论的读者。1. 为什么最小生成树是蓝桥杯/ACM的常驻考点1.1 从P3366模板题的“江湖地位”出发洛谷 P3366 题目名叫【模板】最小生成树输入 n 个点、m 条边要求输出最小生成树的边权和如果图不连通就输出 orz。为什么一道模板题能被反复推荐因为最小生成树是图论里少有的“结论直观、代码量适中、变式丰富”的考点。蓝桥杯的软件类省赛搜索和动态规划是大头但图论题目出现的频率一直不低。尤其是涉及到“若干城市/村庄/基站之间铺设线路要求总代价最小”这类描述本质上就是最小生成树。比赛不会直接告诉你“这题考 MST”而是把问题包装成最优连通方案让你自己抽象成图。这时候如果你只背过模板但不懂算法原理很容易在数据范围或边数密度上栽跟头。1.2 竞赛里最常出现的几种包装方式我整理了近几年的题目和训练中遇到的包装形式最常见的三种是路径铺设型n 个点需要连通给出若干可选边的代价求最小总代价。这是最裸的 MST直接套 Kruskal 或 Prim。最小化最大边要求连通所有点且让“最大的那条边”尽量小。这其实是最小瓶颈生成树问题用 Kruskal 从小到大加边加到图连通时的那条边就是答案不需要真的求完整生成树。超级源点型图中有些点需要特殊处理比如“每个村庄要么自己建发电站要么连到有发电站的村庄”。做法是增加一个虚拟的 0 号点把“自己建站”的代价当成从 0 号点连过来的边然后跑 MST。蓝桥杯和 ICPC 里这种建图思路出现频率非常高。所以学 P3366 不只是学一道题而是把“如何从图论角度建模”这个能力练熟。1.3 先明确一个前提什么是生成树什么是最小生成树很多人把生成树和最小生成树直接划等号其实差了一个关键步骤。生成树是包含图中全部 n 个顶点、且只有 n-1 条边的连通子图。注意它必须是原图的子图不能凭空加边同时要保证所有点连通、没有环。一个图可以有很多棵生成树边数都是 n-1但边权和各不相同。最小生成树Minimum Spanning Tree简称 MST就是在所有生成树里边权和最小的那棵。如果原图本身不连通就不存在生成树更不存在 MST这就是 P3366 里要求输出 orz 的原因。这里有一个竞赛里很重要的直觉生成树边数固定为 n-1所以“最小生成树”本质上是在“选哪些边”上做文章。Kruskal 和 Prim 的贪心策略不同一个盯着边一个盯着点但殊途同归。2. Kruskal把整张图砍成边来贪心2.1 排序并查集的思路为什么是对的Kruskal 的思路非常直白把所有边按权值从小到大排序然后从最小的开始一条一条尝试如果这条边连接的两个点目前还不连通就选它如果已经连通就跳过。直到选了 n-1 条边或者所有边都遍历完。这个做法的正确性依赖一个叫“切分性质”的结论在图中任意一个“切分”把点集分成两部分横跨切分的最小权值边一定属于某棵最小生成树。Kruskal 每次拿的边处理到某个时刻时都等效于某个切分的最小边。更通俗地说先选小边并且用并查集保证不形成环最后一定得到一个最小生成树。我见过不少同学问“如果我先选了小边但这条边其实不在最优解里怎么办”答案是不会。因为贪心策略里“跳过会成环的边”这一步本质上保证了选出的 n-1 条边始终是一个森林每一步选择都不会堵死后续更优的路径。这也是 Kruskal 和“单纯选最小边”之间的区别。2.2 并查集在这个算法里的真正任务Kruskal 的核心数据结构是并查集。它在算法里只做两件事查询两个点是否已经在同一棵树里以及把两棵树合并起来。查询的目的是判断“当前这条边会不会成环”。如果边的两个端点已经连通再连这条边就会形成回路而生成树不能有环所以必须跳过。合并的目的是当选定一条边后把两个连通分量合并成一个保证后续查询结果正确。并查集引入路径压缩和按秩合并后单次操作的复杂度近似常数所以 Kruskal 的总复杂度主要被排序卡住O(m log m)。m 是边数n 是点数。2.3 P3366可提交的Kruskal写法C我平时训练用 C 比较多P3366 的第一版我直接按下面的模板写的AC 没问题#include bits/stdc.h using namespace std; struct Edge { int u, v, w; bool operator(const Edge other) const { return w other.w; } }; vectorint fa, rk; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } bool unite(int x, int y) { x find(x); y find(y); if (x y) return false; if (rk[x] rk[y]) swap(x, y); fa[y] x; if (rk[x] rk[y]) rk[x]; return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; 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()); fa.resize(n 1); rk.resize(n 1, 0); for (int i 1; i n; i) fa[i] i; long long ans 0; int cnt 0; for (auto e : edges) { if (unite(e.u, e.v)) { ans e.w; cnt; if (cnt n - 1) break; } } if (cnt n - 1) cout ans \n; else cout orz\n; return 0; }几个关键点说明一下并查集我用了fa和rk两个数组rk是秩。只写路径压缩也能过但按秩合并能保证更稳定尤其当数据有大量合并操作时。ans用long long。单条边权可能很大n 最多几千总权值叠加后可能超过 int 范围。边排序用的vectorEdge重载了运算符。有些同学喜欢写cmp函数都行但注意排序函数必须满足严格弱序。循环里提前判断cnt n - 1可以省掉无意义的遍历。Python 组同学如果习惯用 Python我建议用sys.stdin.buffer.read()一次性读入然后按行切割。排序直接用sorted(edges, keylambda e: e[2])。整体结构一样只是 Python 常数大P3366 的数据量 m 是 2×10^5 左右PyPy 能过但别用太慢的输入方式。2.4 Kruskal的边界情况与细节Kruskal 实现简单但边界问题容易忽略我在训练时踩过几个坑自环自环的两个端点是同一个点find结果相同unite直接返回 false自然被跳过不需要特判。重边多条相同端点的边里只可能选一条。排序后小权值在前并查集会保证后面的重边被跳过不需要预处理去重。图不连通最终cnt不到n-1就说明图不连通输出 orz 而不是建树失败。孤立点如果一个点没有任何边最后也会导致cnt n-1同样输出 orz。有个细节值得记住Kruskal 在选边过程中如果某条边的两端已经连通说明这条边属于某个环那么它一定不是最小生成树里需要的边。这个“成环边剔除”的逻辑正好对应图论里的“回路性质”。3. Prim从点长出一棵树的贪心3.1 Prim与Dijkstra的异同Prim 是另一个完全不同的贪心视角它从某个起点出发每次找“距离当前已选点集最近”的未选点把它拉进点集并用这个点的所有出边去更新其他未选点的距离值。重复 n-1 次就得到最小生成树。很多人第一次学 Prim 时会觉得它和 Dijkstra 长得一模一样。确实两者的框架都是“维护一个 dist 数组不断选最小然后更新邻居”但本质不同Dijkstra 的dist[i]表示从起点到 i 的最短路径长度更新时做的是dist[v] min(dist[v], dist[u] w)。Prim 的dist[i]表示点 i 到“当前已选点集”的最短边权更新时做的是dist[v] min(dist[v], w)。这个差异导致 Dijkstra 累加路径长度而 Prim 只看单条边的权值。所以 Prim 的正确性依赖的是切分性质而不是最短路径的子路径最优性。3.2 朴素与堆优化复杂度背后的场景Prim 有两种常用实现方式朴素 Prim每次用 O(n) 扫描找最小dist更新时遍历邻接矩阵总复杂度 O(n² m)。适合稠密图尤其是邻接矩阵可以直接表示完整图的时候。堆优化 Prim用优先队列维护候选点总复杂度 O(m log n)。适合稀疏图和 Kruskal 复杂度比较接近。注意一个反直觉的点当图非常稠密比如 n5000 的完全图边数约 1250 万条堆优化 Prim 的 O(m log n) 并不一定比朴素 Prim 的 O(n²) 快因为 log 因子和堆操作常数会拖慢速度。而朴素 Prim 的 O(n²) 是稳定的 2500 万次基本操作实际跑起来非常快。所以我在训练里有个经验n 小但 m 接近 n² 时优先考虑朴素 Primm 是 n 的几倍以内时Kruskal 或堆优化 Prim 都行。这个选型逻辑到后面第 5 节再细说。3.3 P3366可提交的Prim写法Python C片段P3366 的 n 最大约 5000m 最大约 2×10^5属于“边数不算特别多”的稀疏图堆优化 Prim 完全没问题。我给出 Python 可提交版本方便 Python 组的同学直接抄import sys import heapq def main(): data sys.stdin.buffer.read().split() n, m int(data[0]), int(data[1]) graph [[] for _ in range(n 1)] idx 2 for _ in range(m): u int(data[idx]); v int(data[idx 1]); w int(data[idx 2]) idx 3 graph[u].append((v, w)) graph[v].append((u, w)) visited [False] * (n 1) dist [float(inf)] * (n 1) dist[1] 0 pq [(0, 1)] ans 0 cnt 0 while pq: d, u heapq.heappop(pq) if visited[u]: continue if d ! dist[u]: continue visited[u] True ans d cnt 1 for v, w in graph[u]: if not visited[v] and w dist[v]: dist[v] w heapq.heappush(pq, (w, v)) if cnt n: print(ans) else: print(orz) main()这里我加了两道保险visited和d ! dist[u]。优先队列里同一个点可能因为不同距离被加入多次弹出时通过visited判断是否已经进树通过d ! dist[u]跳过过期值。两者其实保留一个也能过但都写更稳。C 的堆优化 Prim 核心片段我顺手也贴一下const int INF 0x3f3f3f3f; vectorvectorpairint,int g(n 1); vectorint dist(n 1, INF); vectorbool vis(n 1, false); priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; dist[1] 0; pq.push({0, 1}); long long ans 0; int cnt 0; while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (vis[u] || dist[u] ! d) continue; vis[u] true; ans d; cnt; for (auto [v, w] : g[u]) { if (!vis[v] w dist[v]) { dist[v] w; pq.push({dist[v], v}); } } }dist[u] ! d在 C 里因为整数比较没问题但注意不要用浮点数存权值竞赛基本不会给浮点边权。3.4 Prim实现里最容易翻车的三个点我从训练和带学弟学妹的经验里总结三个高频翻车点初始化 INF 不够大边权可能到 10^9 甚至更大INF 用0x3f3f3f3f在 C 里通常够但如果你叠加或比较不当可能溢出。Python 用float(inf)最省心。忘记忽略自环自环在 Prim 里不会造成太大问题但当graph[u]里有(u, w)时dist[u]可能被自己的自环更新变小。正确做法是更新前判断v ! u或者直接依赖visited跳过已选点。如果起点不是 1 而是任意点最好统一处理自环。不连通时没有正确判定Prim 结束后如果cnt ! n说明有点永远无法被加入树图不连通。别在这里输出错值。还有一个容易忽略的点邻接矩阵放不下时怎么办。n5000 时int g[5000][5000]约 100MB洛谷老题的内存限制比较紧张C 勉强但 Python 直接炸。所以实际比赛里我很少开纯邻接矩阵除非 n 很小或图确实是完全图。4. 洛谷P3366实战复盘两种写法我都交了一遍4.1 读题和数据分析比写代码更重要P3366 看起来很简单但细看数据范围再动手更稳妥。题目给的 m 上限是 2×10^5这个量级下Kruskal 排序 2×10^5 条边开销可接受堆优化 Prim 堆操作也在可接受范围朴素 Prim 用邻接表存图O(n²)2500 万次扫描C 能过但 Python 可能比较吃力。所以我在本地测试两种算法时C 版 Kruskal 耗时约 30ms 上下Python 版堆优化 Prim 耗时约 300ms 量级这次提交是 Python 用堆优化过的。时间限制一般给 1 秒左右Python 注意输入输出优化就能稳过。读入的关键是别用 Python 的input()一行一行读两万次会拖慢速度。sys.stdin.buffer.read().split()是最省事的加速方案。C 选手记得关流同步。4.2 两种实现的AC过程与耗时对比我把两种实现都在洛谷交过对比结果可以参考实现方式时间复杂度实际耗时数据规模n5000, m≈2×10^5主观难度Kruskal 并查集O(m log m)约 30ms简单堆优化 PrimO(m log n)约 50msC/ 约 300msPython稍难朴素 Prim 邻接表O(n² m)约 100ms 内C中等第一次交 Kruskal 时我 WA 了原因是并查集初始化写成了 0 到 n-1而题目输入是 1 到 n。这类“下标从 1 开始”的坑几乎每个新手都会踩一次。第二次交 Prim 又 WA 了一次因为我在更新 dist 时没判断visited结果已经进树的点被反复更新把 ans 加错了。这些细节不写一遍代码根本记不住。4.3 不连通输出orz之类的坑P3366 输出 orz 的判定我单独拿出来说因为很多题解把它藏在一句代码里但实际考试里真会有人在这里挂掉。用 Kruskal 时cnt n - 1代表选够了边输出答案否则说明原图不连通。用 Prim 时cnt n代表所有点都被拉入树中输出答案否则输出 orz。两个判断条件一个盯着边数一个盯着点数不能混。还有一种情况n1也就是只有一个点。此时生成树需要 0 条边边权和为 0。Kruskal 里初始cnt0n-10满足条件输出 0Prim 里从 1 号点出发cnt 直接到 1也输出 0。两个算法天然兼容这个边界不用特判。5. 答题之前先想三秒钟Kruskal还是Prim5.1 复杂度之外更要看图的稀疏程度很多人问“Kruskal 和 Prim 到底该用哪个”我的答案永远是先看 m 和 n 的关系。稀疏图m 和 n 同一量级比如 m≈n 或 m≈n log nKruskal 通常最顺手因为边排序后直接并查集代码短、常数小。稠密图m 接近 n²比如完全图、网格全连接Prim 更合适。如果 n 不太大几千朴素 Prim 的 O(n²) 反而比堆优化更快因为省去了堆操作的 log 因子。中等密度两种都能过看你自己哪个更熟。比赛比的是稳定写出正确代码的能力不是比谁常数更优。有一个不容易想到的点Kruskal 需要把所有边存下来再排序如果边数是千万级别内存开销很大而 Prim 用邻接表存图边的存储空间相同但不需要额外排序。所以在 m 特别大时Prim 的内存压力往往更小。5.2 竞赛实战中我的选型习惯我个人在 ACM 训练和蓝桥杯备赛中的习惯是默认先看数据范围。n≤1000、m≤100000两种随便写选自己最熟的那个。如果题目描述包含“任意两点之间都有边可选”“网格图”“完全图”等字眼优先 Prim。网格题的边权经常是动态计算的比如曼哈顿距离这时候建图都要现场算用 Prim 边跑边取边权特别方便。如果题目还要求“统计连通块”“判断哪些点连通”等额外信息优先 Kruskal因为并查集本身就是一个连通性工具代码复用率高。如果题目给的是边列表而不是邻接矩阵Kruskal 写起来更短因为不需要建图。另外一个实战技巧做题时如果发现需要在代码里加超级源点比如题目要求“每个点要么自己建站要么连中心站”不管最后用哪个算法建图逻辑都是把 0 号点加进去然后跑最小生成树。这种题别想复杂就是把额外代价当成虚拟边。5.3 从模板到变式MST还能怎么考最小生成树在竞赛里很少只考裸题常见变式我列几个避免以后遇到发懵次小生成树先求 MST然后枚举每条非树边替换树上的最大边求次小权值和。典型题是 POJ 1679蓝桥杯偶尔会把次小生成树的判定包装成“是否存在唯一的生成树”。瓶颈生成树把问题转化为“让最大边最小”。做法是用二分答案 并查集判断连通性或者直接用 Kruskal 从小到大加到连通为止。最小生成森林图本身不连通要求每个连通分量各自生成树总权值最小。其实就是对每个连通块分别跑 Kruskal注意初始cnt的判断逻辑从 n-1 变为总连通块数相关的值。Kruskal 重构树这个偏进阶但在求解“经过路径上最大边权最小”一类问题时非常有用。做法是把 Kruskal 合并两个连通块的过程记录成树形结构新节点权值为当前边权最后形成一棵二叉树。再配合倍增就能快速回答大量询问。我不建议备赛初期就去硬啃重构树但至少要知道它的来历Kruskal 算法本身是可以“可视化”成一个树的构建过程的。理解了这一点后续学重构树会非常快。最后分享一个我自己的习惯每次用 Kruskal 之前我会先在草稿纸上把 n、m 写出来然后心里默念“m log m 的排序能不能承受、内存能不能放下”。遇到 10^5 到 10^6 级别的边数Kruskal 基本无脑冲遇到完全图或者网格图我会转而写 Prim。这套判断帮我在省赛里省下了大量调试时间也希望对你备赛有实际的帮助。