1. 从洛谷P3366说起为什么最小生成树值得反复写最小生成树Minimum Spanning TreeMST是图论里最经典的入门算法之一也是竞赛中的“签到题”级别模板。洛谷P3366这道题堪称最小生成树的“教科书入口”题目描述非常直接给定一个无向图求出最小生成树的边权和如果图不连通则输出orz。你可能觉得这题太基础了但我的经验是越是基础的模板越值得反复“抄写”和推敲。理由很简单最小生成树不光是图论的基石它背后的贪心思想、并查集优化、堆优化技巧在后面很多高级算法里都会反复出现。比如克鲁斯卡尔Kruskal算法的并查集写法几乎原封不动地用在带权并查集、可撤销并查集、最小瓶颈路等问题里普里姆Prim算法的堆优化写法又和迪杰斯特拉Dijkstra算法的堆优化写法长得非常像。把P3366吃透相当于给后面的网络流、最短路、动态树等一大片内容提前打好了地基。这篇文章我会对比三种实现方式朴素Prim、堆优化Prim、Kruskal。我不光会贴出可以直接“抄作业”的完整代码还会把每一步操作的原理和坑讲清楚包括为什么堆优化Prim在某些场景下反而不如朴素Prim、Kruskal的排序为什么可以贪心、并查集路径压缩和按秩合并到底怎么选。不管你是刚接触图论的初学者还是想复习模板的竞赛选手这篇文章都能给你一份实用的参考。2. 题意拆解与算法选型思路2.1 P3366到底在考什么先看题目核心信息输入n个点m条边边带权值。要求输出最小生成树的边权总和。特殊情况原图不连通时输出orz。这里有一个很多初学者容易忽略的点题目并没有保证图一定是连通图。所以模板里必须有一个“判断是否成功生成树”的逻辑。Kruskal里靠并查集统计合并次数就能判断Prim里则需要维护一个vis数组或者统计入树节点数。我在早期写P3366的时候就因为漏了不连通判断样例过了但提交直接WA这个坑后面会详细说。从数据规模来看P3366的常规版本是n5000, m200000个别数据范围还会更大。在这个数据量下朴素Prim的O(n^2)其实已经能过5000的平方是2500万但为了追求通用性我们通常还是会把三种写法都掌握。2.2 三种算法的适用场景与选择逻辑算法时间复杂度核心数据结构适用场景朴素PrimO(n^2)数组维护距离稠密图m接近n^2n在5000以内堆优化PrimO((nm)log n)优先队列vis数组稀疏图m远小于n^2n较大KruskalO(m log m)并查集边集排序稀疏图m在10万级别需要简单判连通为什么会有这样的适用差异核心在于两种算法扩展最小生成树的视角不同Prim是从“点”的角度生长每次找一个离当前树最近的未入树节点把它的距离累加并把它的邻边更新到候选池里。所以它天然适合点少边多的稠密图。Kruskal是从“边”的角度合并把所有边按权值从小到大排序逐个尝试加入生成树能加就加直到形成n-1条边。所以它天然适合边数可控、排序代价能接受的图。我在做题时对选型有个经验法则如果m接近n^2直接写朴素Prim如果m接近n的常数倍写Kruskal或堆优化Prim如果题目里明确提到判连通Kruskal写起来最顺手因为加边次数直接对应联通分量合并次数。3. 三种代码实现详解3.1 Kruskal 并查集最直观的贪心Kruskal的核心逻辑是“边排序 并查集判环”。为什么按边权从小到大加边就一定对因为最小生成树要的是全局总权值最小而任何一颗生成树都恰好有n-1条边如果我们能保证每次加入的边都是“当前不产生环的最小边”最终得到的树就是最优的。这是一个典型的贪心策略而且可以严格证明如果某条最小边没有被选入最优解那么把它加进去替换掉路径上的一条更重边一定能得到更优解或相同解。下面是我在P3366里用的Kruskal模板#include bits/stdc.h using namespace std; struct Edge { int u, v, w; bool operator(const Edge other) const { return w other.w; } }; const int MAXN 5005; const int MAXM 200005; int fa[MAXN], rnk[MAXN]; void init(int n) { for (int i 1; i n; i) { fa[i] i; rnk[i] 1; } } int find(int x) { if (fa[x] ! x) fa[x] find(fa[x]); return fa[x]; } bool unite(int x, int y) { x find(x); y find(y); if (x y) return false; if (rnk[x] rnk[y]) swap(x, y); fa[y] x; rnk[x] rnk[y]; return true; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin n m; vectorEdge edges; edges.reserve(m); for (int i 0; i m; i) { int u, v, w; cin u v w; edges.push_back({u, v, w}); } sort(edges.begin(), edges.end()); init(n); long long ans 0; int cnt 0; for (const Edge 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; }这块代码有几个细节值得多说两句并查集的查询路径压缩find函数里用了递归路径压缩写法最简洁。但在某些递归深度极深的场景比如树退化成链可能会爆栈。竞赛里通常n在10万以内问题不大但如果你在工程环境里写建议改成迭代版本。按秩合并rnk[x] rnk[y]时交换保证树高尽量平衡。实际上只写路径压缩就够了加上按秩合并后整体复杂度接近常数级写起来也只多三行。排序结构体的比较函数我直接用operator重载也可以用sort加lambda写看个人习惯。注意在sort里千万别用标准库要求严格弱序相等边最好返回false。3.2 朴素Prim从点向外生长朴素Prim的思路是维护一个dis数组表示每个未入树节点到当前生成树的最短距离。每次从dis里选出最小且未访问的节点加入树中然后更新它所有邻居的dis。为什么它能保证全局最优和Kruskal一样也是贪心生成树每增加一个节点必须有一条边连接这个节点和已有树。要保证最终总权值最小每次扩展时选择“当前可达未入树节点的最短边”是安全的。这本质上和Dijkstra很相似区别在于Prim的距离是到“整个树”的距离而Dijkstra是到“源点”的距离。#include bits/stdc.h using namespace std; const int MAXN 5005; const int INF 0x3f3f3f3f; int G[MAXN][MAXN]; int dis[MAXN]; bool vis[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin n m; memset(G, 0x3f, sizeof(G)); for (int i 1; i n; i) G[i][i] 0; for (int i 0; i m; i) { int u, v, w; cin u v w; G[u][v] min(G[u][v], w); G[v][u] min(G[v][u], w); } memset(dis, 0x3f, sizeof(dis)); dis[1] 0; long long ans 0; int cnt 0; for (int i 1; i n; i) { int u -1; int minDis INF; for (int j 1; j n; j) { if (!vis[j] dis[j] minDis) { minDis dis[j]; u j; } } if (u -1) { cout orz \n; return 0; } vis[u] true; ans dis[u]; cnt; for (int v 1; v n; v) { if (!vis[v] G[u][v] dis[v]) { dis[v] G[u][v]; } } } cout ans \n; return 0; }这个写法有几个要点邻接矩阵初始化memset(G, 0x3f, sizeof(G))把矩阵每个字节置为0x3f得到的整数是0x3f3f3f3f大约是10亿远大于边权上限可以安全当作无穷大。重边处理输入里可能包含重边所以要取min保留最小权值。这个问题在Kruskal里天然不明显因为排序后最小边会先被尝试但在Prim的邻接矩阵里如果不取min后读入的大边可能会覆盖小边。起点选择我用dis[1] 0作为起点这没问题无论从哪个点开始生成树的总权值都一样。朴素Prim的复杂度是O(n^2)当n5000时循环次数约2500万一秒内没问题。但如果把P3366的数据范围升级到n30000这种写法就会超时必须换堆优化。3.3 堆优化Prim优先队列驱动的扩展堆优化Prim是朴素Prim的“升级版”它把“每次找最小dis”这个O(n)操作交给优先队列复杂度降到O((nm)log n)。这其实就是Dijkstra的堆优化写法只是更新时的“距离”含义不同。它的缺陷是稠密图下log因子反而让常数变大所以一般只在稀疏图时使用。#include bits/stdc.h using namespace std; struct Edge { int to, w; }; struct Node { int u, dis; bool operator(const Node other) const { return dis other.dis; } }; const int MAXN 5005; const int INF 0x3f3f3f3f; vectorEdge graph[MAXN]; int dis[MAXN]; bool vis[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin n m; for (int i 0; i m; i) { int u, v, w; cin u v w; graph[u].push_back({v, w}); graph[v].push_back({u, w}); } memset(dis, 0x3f, sizeof(dis)); priority_queueNode, vectorNode, greaterNode pq; dis[1] 0; pq.push({1, 0}); long long ans 0; int cnt 0; while (!pq.empty()) { Node cur pq.top(); pq.pop(); int u cur.u; if (vis[u]) continue; vis[u] true; ans cur.dis; cnt; for (const Edge e : graph[u]) { int v e.to; if (!vis[v] e.w dis[v]) { dis[v] e.w; pq.push({v, e.w}); } } } if (cnt n) cout ans \n; else cout orz \n; return 0; }这里有一个特别容易写错的地方堆里面可能同时存在同一个节点的多个“历史候选值”比如先用10更新过一次后来发现另一条边是8这时候dis已经变成8堆里却还有一份(10)的旧记录。所以在pop出来之后必须用vis数组判断这个节点是不是已经被选入树中。这个if(vis[u]) continue;是性能的关键没有它可能会重复处理同一个节点。我在实际测试中发现堆优化Prim在n5000, m200000的稠密数据集上比朴素Prim慢很多原因是优先队列的log开销和频繁的push操作。所以这道题如果限定n在5000以内朴素Prim反而是最优选择。这也是为什么我说“模板不是越高级越好适合数据范围才是关键”。4. 三种写法对比与避坑要点4.1 代码风格与数据结构对比对比维度Kruskal朴素Prim堆优化Prim建图方式边集数组邻接矩阵邻接表核心操作排序并查集合并双层循环维护dis优先队列邻接表遍历空间复杂度O(m)O(n^2)O(nm)判连通方式统计合并次数cntn-1选点失败时u-1统计入树节点cntn典型耗时表现排序是瓶颈双层循环是瓶颈堆操作是瓶颈从代码量看Kruskal的代码量最少逻辑也最直白。从记忆角度看Kruskal只需要记住并查集那三件套init、find、unite很适合比赛时快速默写。Prim系列的代码和Dijkstra高度重合所以如果你要背Dijkstra模板Prim几乎顺手就记住了。4.2 重边和自环问题P3366并没有保证输入无重边、无自环所以模板要能处理这些情况Kruskal自环uv在unite时find(u)find(v)会直接返回false所以自环天然被忽略重边排序后只取最小的那条取到更大的重边时并查集会拒绝合并所以Kruskal天然免疫重边问题。朴素Prim邻接矩阵必须用min覆盖重边自环G[i][i]0不会影响dis更新。堆优化Prim邻接表直接存储所有重边更新时取dis[v]较小值重边的存在最多多几次push不影响正确性。所以如果你不想处理重边Kruskal是最省事的。4.3 并查集find递归爆栈问题前面提到了递归路径压缩可能爆栈这里给一个迭代版的findint find(int x) { while (fa[x] ! x) { fa[x] fa[fa[x]]; x fa[x]; } return x; }这个写法叫“路径减半”每次向上跳两级常数很小也不会爆栈。在绝大多数场景下效果和递归版一样甚至更快。竞赛代码里其实递归版更容易接受因为简洁但如果你在Windows环境写某些OJ题目时遇到段错误可以考虑换成迭代版排查。4.4 溢出问题P3366的边权上限通常不会太大但最小生成树的边权和可能达到10^10级别比如n10^5每条边权10^5总和就是10^10。如果直接存int会溢出必须用long long。这三份模板我都已经用long long ans来存结果这是很多新手最容易忽略的地方。同样的道理也适用于dis数组如果你用int存dis而边权上限很大初始化时设置的INF0x3f3f3f3f约10亿可能不够用因为10亿并不是真正的无穷大累加时会出错。稳妥的做法是直接把dis设为long longINF设为0x3f3f3f3f3f3f3f3f。5. 常见问题与排查技巧实录5.1 为什么我Kruskal样例过了但提交WA我早期写Kruskal时遇到过这类问题最后发现是cnt判断写错了。有人会在循环结束后直接判断cnt n但Kruskal的合并次数应该等于n-1树有n-1条边合并n-1次后所有点都在一棵树里。如果无向图本身有n个节点当合并次数达到n-1时一定形成了一颗生成树反之如果循环完cnt n-1说明图不连通。还有一个隐蔽问题unite中如果在cnt达到n-1之前就遇到边遍历完说明边不够此时输出orz。这同样代表图不连通因为连通图至少需要n-1条边。5.2 Prim为什么死循环如果你在朴素Prim里写了while(true)循环且没有在“找不到u”时退出那么在不连通图里就会真的死循环。我的习惯是每次循环选点前先判断if (u -1)直接输出orz并结束。堆优化Prim里如果cnt ! n在循环结束后统一判断也行。5.3 堆优化Prim性能反而不如预期堆优化Prim常被“推荐”成万能模板但它在完全图里会非常慢。我做过一个基准测试n5000的完全图朴素Prim用时约13ms堆优化Prim由于要处理近2500万条邻接表边并反复push耗时反而到200ms以上。所以在比赛里遇到“稠密图”字眼时优先考虑朴素Prim和邻接矩阵。5.4 排序结构体的严格弱序问题有同学喜欢把operator写成bool operator(const Edge other) const { return w other.w; }这是错的。sort要求严格弱序strict weak ordering会破坏它可能导致排序结果不确定。标准写法是return w other.w;。如果两条边的权值相等谁先谁后不影响最终答案但排序算法必须能处理相等元素。6. 实战扩展当P3366的模板用在其他题目里最小生成树模板的用途远不止于“求边权和”。下面这几个常见变体都是基于这份模板加一点东西就能解决的6.1 次小生成树思路是先跑一遍MST然后枚举每条不在树上的边(u,v,w)尝试替换树中u到v路径上的最大边。如果替换后总权值最小且大于MST权值就是次小生成树。这需要在MST的树边上预处理LCA和路径最大值但核心第一步仍然是Kruskal或Prim。6.2 最小瓶颈路在无向图中求两点间路径上最大边权的最小值。我们可以先用Kruskal从小到大加边目标点第一次连通时的边权就是答案。这其实就是Kruskal过程的实时判连通完全不需额外写新的算法。6.3 带权并查集扩展P3366里的unite只做了秩合并但很多题目会在合并时同时维护节点到根节点的权值关系。比如“食物链”这题就是用带权并查集维护三种关系。模板的核心思想不变只是在unite和find时多更新两个数组。我对新手的建议是先把P3366的并查集背到条件反射再去看带权版本会轻松很多。6.4 最小生成树计数的起点如果题目要求生成树的棵数需要用到矩阵树定理Kirchhoff定理和MST算法没有直接关系但要理解生成树的边集结构还是绕不开对MST构造过程的理解。7. 如何把模板变成自己的肌肉记忆很多同学收藏了一堆模板但到了考场还是写不出来。我个人的训练方法是这样第一步默写打开编辑器不查资料在15分钟内默写出Kruskal和朴素Prim的完整代码。默写不追求变量名漂亮追求一次通过样例。第二步变式练习把P3366改成求最大生成树排序cmp反过来即可改成输出生成树边集存一下unite成功的边改成判断图是否连通统计连通分量数。这些变式强制你理解每一行的作用而不是死记硬背。第三步卡时间给自己设定时间限制比如5分钟内完成Kruskal的编写和样例测试。竞赛里“模板题”的送分题属性就是要求你“秒杀”没有犹豫时间。最近我做题还有一个体会P3366的模板代码虽然简单但它几乎覆盖了图论入门阶段最核心的三样技能——贪心证明、并查集、优先队列。把这三样揉到一道题里掌握扎实后面学最短路、拓扑排序、差分约束时很多代码框架都是平移获得。所以我建议你别只满足于“AC”而是把三种写法都分别提交一遍看看不同写法的耗时差异再手写一遍伪代码解释为什么贪心成立。这个过程走完你才算真正吃透了这个模板。最后分享一个小技巧我平时会在本地维护一份“算法模板速查表”里面不需要长篇解释只需要三份可直接编译运行的代码加一行注释说明适用场景。比赛前五分钟扫一遍考场上就有底气。P3366的这三份模板就是我这套速查表里最早收录的内容之一。