1. 从洛谷P3366说起：为什么最小生成树值得反复写
最小生成树（Minimum Spanning Tree，MST）是图论里最经典的入门算法之一，也是竞赛中的“签到题”级别模板。洛谷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的常规版本是n<=5000, m<=200000，个别数据范围还会更大。在这个数据量下，朴素Prim的O(n^2)其实已经能过（5000的平方是2500万），但为了追求通用性，我们通常还是会把三种写法都掌握。
2.2 三种算法的适用场景与选择逻辑
| 算法 | 时间复杂度 | 核心数据结构 | 适用场景 |
|---|---|---|---|
| 朴素Prim | O(n^2) | 数组维护距离 | 稠密图（m接近n^2），n在5000以内 |
| 堆优化Prim | O((n+m)log n) | 优先队列+vis数组 | 稀疏图（m远小于n^2），n较大 |
| Kruskal | O(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; vector<Edge> 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)，当n=5000时循环次数约2500万，一秒内没问题。但如果把P3366的数据范围升级到n=30000，这种写法就会超时，必须换堆优化。
3.3 堆优化Prim：优先队列驱动的扩展
堆优化Prim是朴素Prim的“升级版”，它把“每次找最小dis”这个O(n)操作交给优先队列，复杂度降到O((n+m)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; vector<Edge> 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_queue<Node, vector<Node>, greater<Node>> 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在n=5000, m=200000的稠密数据集上比朴素Prim慢很多，原因是优先队列的log开销和频繁的push操作。所以这道题如果限定n在5000以内，朴素Prim反而是最优选择。这也是为什么我说“模板不是越高级越好，适合数据范围才是关键”。
4. 三种写法对比与避坑要点
4.1 代码风格与数据结构对比
| 对比维度 | Kruskal | 朴素Prim | 堆优化Prim |
|---|---|---|---|
| 建图方式 | 边集数组 | 邻接矩阵 | 邻接表 |
| 核心操作 | 排序+并查集合并 | 双层循环维护dis | 优先队列+邻接表遍历 |
| 空间复杂度 | O(m) | O(n^2) | O(n+m) |
| 判连通方式 | 统计合并次数cnt==n-1 | 选点失败时u==-1 | 统计入树节点cnt==n |
| 典型耗时表现 | 排序是瓶颈 | 双层循环是瓶颈 | 堆操作是瓶颈 |
从代码量看，Kruskal的代码量最少，逻辑也最直白。从记忆角度看，Kruskal只需要记住并查集那三件套（init、find、unite），很适合比赛时快速默写。Prim系列的代码和Dijkstra高度重合，所以如果你要背Dijkstra模板，Prim几乎顺手就记住了。
4.2 重边和自环问题
P3366并没有保证输入无重边、无自环，所以模板要能处理这些情况：
- Kruskal：自环（u==v）在
unite时find(u)==find(v)会直接返回false，所以自环天然被忽略；重边排序后只取最小的那条，取到更大的重边时并查集会拒绝合并，所以Kruskal天然免疫重边问题。 - 朴素Prim：邻接矩阵必须用
min覆盖重边；自环G[i][i]=0，不会影响dis更新。 - 堆优化Prim：邻接表直接存储所有重边，更新时取
dis[v]较小值，重边的存在最多多几次push，不影响正确性。
所以如果你不想处理重边，Kruskal是最省事的。
4.3 并查集find递归爆栈问题
前面提到了递归路径压缩可能爆栈，这里给一个迭代版的find：
int find(int x) { while (fa[x] != x) { fa[x] = fa[fa[x]]; x = fa[x]; } return x; }这个写法叫“路径减半”，每次向上跳两级，常数很小，也不会爆栈。在绝大多数场景下效果和递归版一样，甚至更快。竞赛代码里其实递归版更容易接受，因为简洁；但如果你在Windows环境写某些OJ题目时遇到段错误，可以考虑换成迭代版排查。
4.4 溢出问题
P3366的边权上限通常不会太大，但最小生成树的边权和可能达到10^10级别（比如n=10^5，每条边权10^5，总和就是10^10）。如果直接存int，会溢出，必须用long long。这三份模板我都已经用long long ans来存结果，这是很多新手最容易忽略的地方。
同样的道理也适用于dis数组：如果你用int存dis，而边权上限很大，初始化时设置的INF=0x3f3f3f3f（约10亿）可能不够用，因为10亿并不是真正的无穷大，累加时会出错。稳妥的做法是直接把dis设为long long，INF设为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常被“推荐”成万能模板，但它在完全图里会非常慢。我做过一个基准测试：n=5000的完全图，朴素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的这三份模板，就是我这套速查表里最早收录的内容之一。
