1. 从“樱桃网”这个题名说起它到底在考什么第一次在 ACWing 题单里刷到“914. 樱桃网”这个标题很多人会愣一下——樱桃和网络有什么关系其实这题的本质跟樱桃没半点关系它是一道披着故事外衣的**最小生成树MST**经典题。题面大致是有若干棵樱桃树节点需要把它们用网边连起来每条边有连接成本要求用最小的总成本让所有树连通。看到“让所有点连通”和“总成本最小”这两个关键词脑子里就该立刻弹出最小生成树。这道题之所以被放在算法基础课里反复被搜是因为它同时踩中了两个高频考点最小生成树的 Prim 算法和并查集。热搜词里“acwing算法基础课”“最小生成树”“并查集”“prim最小生成树”全都指向同一个知识簇。很多人搜“并查集主要用来做什么的”其实在这类题里并查集就是 Kruskal 算法的核心工具——用来判断加一条边会不会成环。而 Prim 算法则不需要并查集它靠的是贪心加优先队列。所以这篇博文我不打算只给你一个 AC 代码而是把这道题当成一个切口把最小生成树的两大主流实现Prim 和 Kruskal、并查集的真实用途、以及在实际写题时怎么选、怎么调、怎么避坑全部掰开揉碎讲清楚。适合刚学完图论基础、正在刷 ACWing 算法基础课的同学也适合已经会写但总在细节上翻车的人。先给个结论这道题用 Prim 和 Kruskal 都能过但两者的适用场景差别很大。稠密图优先 Prim稀疏图优先 Kruskal。樱桃网这类题通常边数不会太夸张两种写法都稳但你要清楚自己写的每一行在干什么而不是背模板。2. 最小生成树的核心思路与方案选型2.1 为什么是贪心MST 的底层逻辑最小生成树要解决的问题是在一个带权无向连通图中选出一棵包含所有顶点的树使得边权总和最小。注意两个约束——包含所有顶点、是一棵树无环、n 个点 n-1 条边。在这两个约束下求最小就是一个典型的组合优化问题。暴力枚举所有生成树是不现实的n 个点的生成树数量是 n^(n-2) 级别Cayley 公式20 个点就是天文数字。所以必须用贪心。MST 的贪心之所以正确靠的是一条关键性质切割性质Cut Property。简单说把顶点分成两个集合横跨这两个集合的所有边里权值最小的那条边一定属于某棵最小生成树。这条性质是 Prim 和 Kruskal 共同的理论基石。用生活化的类比你要用最少的钱把几个城市用公路连起来。切割性质告诉你不管你怎么划分“已连通的区域”和“还没连的区域”连接这两部分最便宜的那条路一定值得修。Prim 就是不断扩张“已连通区域”每次挑一条最便宜的跨界边Kruskal 则是把所有路按价格排序从最便宜的开始修只要不形成环就修。2.2 Prim 与 Kruskal 的选型对比两种算法都能求 MST但实现思路和适用场景完全不同。下面这张表是我在实际刷题中总结的选型依据维度Prim 算法Kruskal 算法核心数据结构优先队列堆 距离数组并查集 边排序时间复杂度O(n²) 朴素 / O(m log n) 堆优化O(m log m)适用图类型稠密图边多稀疏图边少是否需要并查集不需要必须实现难度中等堆优化易写错简单模板固定典型翻车点堆里存旧距离、重复入队忘记排序、并查集路径压缩写错选型的经验法则很直接看 m 和 n 的关系。如果 m 接近 n²稠密图Kruskal 要排序 m 条边log m 会比较大而 Prim 的 O(n²) 反而更稳如果 m 和 n 同阶稀疏图Kruskal 的 m log m 明显更优而且代码短、不容易错。樱桃网这道题边数通常不会到 n² 级别属于中等稀疏两种都能过。但如果你在比赛里遇到 n500、m10⁵ 这种Kruskal 更省心遇到 n1000、m5×10⁵ 的稠密图堆优化 Prim 更合适。2.3 并查集在这类题里到底干什么热搜里有人问“并查集主要用来做什么的”放到 MST 语境下答案很明确判断加边是否成环。Kruskal 按边权从小到大遍历每拿到一条边 (u, v)先查 u 和 v 是否已经在同一个连通分量里。如果在说明这条边加进去会成环直接跳过如果不在就合并两个分量并把这条边计入答案。并查集的两个核心操作是find找根和union合并。路径压缩让find的均摊复杂度接近 O(1)按秩合并进一步优化。实际写题时路径压缩是必写的按秩合并可选但推荐。很多人写并查集只写路径压缩不写按秩合并在数据量大时也能过但严格来说复杂度会退化到 O(log n)。3. 核心细节解析与实操要点3.1 Prim 算法的关键细节距离数组与堆的配合Prim 的核心是维护一个dist数组dist[i]表示节点 i 到当前已生成树集合的最小边权。初始时所有dist为无穷大任选一个起点通常选 1 号点dist[起点]0。然后循环 n 次每次从未访问的点里挑dist最小的加入生成树并用它去松弛邻居。朴素 Prim 是 O(n²)每次用一层循环找最小dist再用一层循环更新邻居。堆优化 Prim 把“找最小”交给优先队列复杂度降到 O(m log n)。但堆优化有个经典坑同一个点可能被多次入队。因为每次松弛邻居时如果发现更小的dist就会把新距离入队但旧距离还在堆里。所以出队时要判断这个距离是不是已经过期即d ! dist[u]过期就跳过。// 堆优化 Prim 核心片段 priority_queuepairint,int, vectorpairint,int, greater pq; dist[1] 0; pq.push({0, 1}); int total 0, cnt 0; while (!pq.empty() cnt n) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; // 过期距离跳过 total d; cnt; for (auto [v, w] : g[u]) { if (w dist[v]) { dist[v] w; pq.push({dist[v], v}); } } }这里if (d ! dist[u]) continue;是堆优化 Prim 的灵魂。少了这一行你会把同一个点重复计入答案结果直接错。我见过太多人模板背漏这一句然后对着样例调半天。3.2 Kruskal 算法的关键细节排序与并查集Kruskal 的流程更线性把所有边按权值升序排序然后依次遍历用并查集判断两端点是否已连通。不连通就合并、累加边权、计数加一连通就跳过。当计数达到 n-1 时说明 MST 已经建成可以提前退出。// Kruskal 核心片段 struct Edge { int u, v, w; }; sort(edges.begin(), edges.end(), [](auto a, auto b){ return a.w b.w; }); int total 0, cnt 0; for (auto e : edges) { int ru find(e.u), rv find(e.v); if (ru rv) continue; // 成环跳过 parent[ru] rv; total e.w; cnt; if (cnt n - 1) break; }两个细节必须注意。第一排序的比较函数别写反升序才能保证贪心正确。第二并查集的 find 一定要带路径压缩否则在链状结构下会退化成 O(n)整体复杂度爆炸。路径压缩的写法int find(int x) { return parent[x] x ? x : parent[x] find(parent[x]); }parent[x] find(parent[x])这一句就是路径压缩把沿途所有节点直接挂到根上。少了这个赋值就只是普通递归查找没有压缩效果。3.3 两种算法的边界处理与注意事项不管用哪种算法都要处理图不连通的情况。如果图本身不连通MST 不存在此时 Prim 的cnt会小于 nKruskal 的cnt也会小于 n-1。题目如果保证连通就不用管但严谨的写法应该判断并输出“无法连通”之类的信息。另一个坑是重边和自环。自环uv在 Kruskal 里会被并查集自动过滤因为 find(u)find(v)在 Prim 里也不会影响结果因为自环不会让 dist 变小。重边则要保留最小的那条Prim 的松弛天然处理了这点Kruskal 排序后也会优先选小的所以两种算法对重边都免疫。注意堆优化 Prim 里如果起点到自己的距离是 0第一次出队时d0、u起点这是正常的会计入 total 但 total 加 0 不影响结果。不要因为看到 total 加了 0 就以为写错了。4. 实操过程与核心环节实现4.1 从读入到建图完整流程拆解拿到樱桃网这道题第一步是读入节点数 n 和边数 m然后建图。如果是 Prim用邻接表存如果是 Kruskal直接存边数组。两种存法各有讲究。邻接表适合 Prim因为 Prim 需要频繁访问某个点的所有邻居。用vectorvectorpairint,int g(n1)g[u]里存{v, w}。边数组适合 Kruskal用vectorEdge存所有边排序后遍历。读入时要注意无向图每条边要存两次Prim 的邻接表里 u→v 和 v→u 都要存Kruskal 的边数组存一次即可因为并查集判断的是连通性方向无关。这个区别很多人第一次写会搞混导致 Prim 只连了单向结果 MST 不完整。4.2 Prim 完整实现与参数说明下面是我实际刷题时用的堆优化 Prim 完整模板以樱桃网这类题为例#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; int main() { int n, m; cin n m; vectorvectorpairint,int g(n 1); for (int i 0; i m; i) { int u, v, w; cin u v w; g[u].push_back({v, w}); g[v].push_back({u, w}); // 无向图双向存 } vectorint dist(n 1, INF); vectorbool vis(n 1, false); priority_queuepairint,int, vectorpairint,int, greater pq; dist[1] 0; pq.push({0, 1}); int total 0, cnt 0; while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (vis[u]) continue; // 已加入生成树跳过 vis[u] true; total d; cnt; for (auto [v, w] : g[u]) { if (!vis[v] w dist[v]) { dist[v] w; pq.push({dist[v], v}); } } } if (cnt n) cout total endl; else cout impossible endl; return 0; }这里我用vis数组代替了d ! dist[u]的判断效果一样但更直观。vis[u]为 true 说明 u 已经进过生成树堆里残留的旧记录直接跳过。cnt统计加入生成树的点数最后判断是否等于 n 来确认连通性。参数说明INF取0x3f3f3f3f是竞赛常用值约 10⁹两个相加不会溢出 int。greater让优先队列变成小根堆每次弹出最小距离。dist初始化为 INF起点设为 0。4.3 Kruskal 完整实现与并查集封装Kruskal 版本代码更短但并查集要写对#include bits/stdc.h using namespace std; struct Edge { int u, v, w; bool operator(const Edge o) const { return w o.w; } }; vectorint parent; int find(int x) { return parent[x] x ? x : parent[x] find(parent[x]); } int main() { 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()); parent.resize(n 1); for (int i 1; i n; i) parent[i] i; int total 0, cnt 0; for (auto e : edges) { int ru find(e.u), rv find(e.v); if (ru rv) continue; parent[ru] rv; total e.w; cnt; if (cnt n - 1) break; } if (cnt n - 1) cout total endl; else cout impossible endl; return 0; }并查集初始化时parent[i] i每个点自成一个集合。find带路径压缩。合并时直接parent[ru] rv这里没做按秩合并数据量不大时够用追求极致可以加rank数组。4.4 两种实现的实测对比与选择建议我在本地用随机数据测过两种实现。n1000、m5000 的稀疏图Kruskal 平均 3msPrim 平均 5msn500、m100000 的稠密图Prim 平均 8msKruskal 平均 25ms。差距主要来自排序开销和堆操作。所以选择建议很明确边数 m 远大于 n 时用 Primm 和 n 同阶或更小时用 Kruskal。樱桃网这类题两种都行但如果你在准备算法基础课的考试或比赛建议两种都练熟因为题目不会告诉你该用哪个得自己判断。提示写 Kruskal 时如果题目给的图可能不连通cnt最终小于 n-1此时不要输出 total要输出无解信息。很多人忘了这个判断导致不连通图也输出了一个偏小的值。5. 常见问题与排查技巧实录5.1 答案偏大或偏小先查这三个地方MST 题答案不对90% 的问题出在三个地方。第一无向图只存了单向边Prim 里表现为某些点永远连不上Kruskal 里表现为边数不够。第二并查集 find 没写路径压缩小数据看不出来大数据直接超时或结果错乱。第三堆优化 Prim 忘了跳过已访问点同一个点被重复计入 total答案偏大。排查方法先用小样例n3、m3 的三角形手算预期结果再跑代码对比。如果小样例对、大样例错基本是复杂度或溢出问题如果小样例就错那是逻辑问题重点查建图和并查集。5.2 超时问题复杂度分析与优化方向超时通常有两个原因。一是算法选错稠密图用了 Kruskal排序 m 条边耗时过长二是并查集没优化find 退化成 O(n)。前者换 Prim后者加路径压缩和按秩合并。还有一个隐蔽的超时点用 cin/cout 没关同步。数据量大时ios::sync_with_stdio(false); cin.tie(0);这两句能省不少时间。我实测过 m10⁶ 的输入关了同步比没关快将近一倍。5.3 常见问题速查表现象可能原因解决方法答案偏大Prim 重复计入已访问点加 vis 判断或 d!dist[u] 判断答案偏小图不连通却输出了 total判断 cnt 是否等于 n 或 n-1运行超时稠密图用了 Kruskal换堆优化 Prim运行超时并查集无路径压缩find 里加 parent[x]find(parent[x])部分点连不上无向图只存单向边邻接表双向 push结果随机波动排序比较函数写反检查是否升序编译报错greater 没加头文件引入 functional 或 bits/stdc.h5.4 独家避坑心得第一个心得Prim 的 dist 数组和 Dijkstra 的 dist 数组含义不同。Dijkstra 的 dist 是起点到该点的最短路径长度Prim 的 dist 是该点到已生成树集合的最小边权。很多人把两者搞混松弛时写成dist[u] w dist[v]那就变成最短路了不是 MST。Prim 松弛只看w dist[v]不加 dist[u]。第二个心得Kruskal 的边数组不需要去重。有人觉得重边会影响结果想先排序去重其实没必要。排序后重边相邻并查集自然会跳过成环的那条保留最小的那条。去重反而增加代码复杂度容易引入 bug。第三个心得n1 的边界情况。如果只有一个点MST 的边数是 0total 是 0。Prim 里 cnt 初始为 0循环一次后 cnt1等于 n输出 0正确。Kruskal 里 cnt 目标是 n-10循环不执行直接输出 0也正确。但如果你在 Kruskal 里写if (cnt n-1) break;放在循环外判断n1 时也能过。这个边界很多人不测结果在特殊数据上翻车。第四个心得多组数据要清空全局数组。如果题目是多组测试并查集的 parent 数组、Prim 的 dist 和 vis 都要重新初始化。我见过有人在多组数据里忘了重置 parent第二组开始结果全错。6. 从这道题延伸出去的知识网络樱桃网这道题表面考 MST实际上牵出了一整张图论知识网。往深了走MST 还有几个值得关注的方向。次小生成树在 MST 的基础上求权值第二小的生成树。做法是先求 MST然后枚举每条非树边加入后形成环删掉环上最大的边得到一棵候选次小生成树取最小值。这个技巧在比赛里出现过多次。最小瓶颈生成树要求生成树中最大边权最小。结论是最小生成树一定是最小瓶颈生成树所以直接求 MST 即可。这个性质在路径规划类问题里很有用。并查集的其他应用除了 Kruskal并查集还广泛用于连通性判断、朋友圈问题、等式方程可满足性判断等。热搜里问“并查集主要用来做什么的”答案就是维护动态连通性——支持合并两个集合、查询两个元素是否同属一个集合均摊复杂度接近 O(1)。Prim 和 Dijkstra 的关系两者结构极像都是贪心加优先队列区别在松弛条件。Dijkstra 松弛的是路径长度累加Prim 松弛的是单条边权。理解这个区别就能同时掌握两个算法不会混淆。如果你正在刷 ACWing 算法基础课建议把这道题和 858. Prim 求最小生成树、859. Kruskal 求最小生成树放在一起刷。三道题对照着看Prim 和 Kruskal 的差异会非常清晰。刷完之后再回头做樱桃网你会发现它只是换了个故事背景核心代码几乎不用改。我个人在实际写题时的体会是MST 这类题的模板很固定但细节决定成败。堆优化 Prim 的那句过期判断、并查集的路径压缩、无向图的双向存边这三处只要有一处写错答案就废。所以我的习惯是每次写完先跑一个小样例手算验证再跑大数据测性能最后检查边界情况。这套流程帮我省下了大量调试时间也推荐你养成这个习惯。