本讲定位：图论系列第十讲。上一讲的并查集在这里立刻兑现——Kruskal 就是”排序 + 并查集”，你在第 09 讲第 4.2 节（P1111 修复公路）其实已经写过一遍了，本讲只是给它一个名字和一个证明。本讲做了七组实测，三个数字值得先记住：把 Prim 的松弛式写成 Dijkstra 的
dis[u] + w（少写一个字都不像错），在连通图上实测错 90.93%——这是本系列至今错误率最高的单一写法；Kruskal 的用时有 77%～98% 花在排序上，那个if (++cnt == n-1) break只是锦上添花；而在平面点两两建完全图（$n=6000$）时，朴素 $O(n^2)$ Prim 比 Kruskal 快 10.3 倍、省 77 倍内存（0.169 s / 3.7 MB vs 1.740 s / 285 MB）。另外实测确认了两条常被当作口诀背的结论：最小瓶颈路就是 MST 上的路径（6000 组对拍零不一致），以及最小生成树的权值和唯一但树本身常常不唯一（小图上 21.8% 不唯一）。文中所有代码经g++ -O2 -std=c++14 -Wall编译运行，P3366、P2330、P2872、P1991、P1547 与洛谷官方样例核对通过。前置知识：第 09 讲并查集（硬前置，Kruskal 的零件）；第 05 讲 Dijkstra（Prim 和它是同一个骨架，本讲会逐行对照）；第 01 讲的存图选择（本讲第 4.5 节是”邻接矩阵不可替代”的第二个场合，第一个是第 07 讲的 Floyd）。第 8 节末尾和第 9 讲的 P1967 要用到 LCA（第 12 讲），届时可以回头再看。
适合对象：第 1～6 节标 J（CSP-J 复赛必会）；第 7、8 节标 S；第 9、10 节标 S⭐，第一轮可整节跳过。
$n$ 个村庄、$m$ 条可以修的路，每条路有造价。选一些路修起来，使得任意两个村庄互通，总造价最小。
先把两件事说清楚。
第一，答案一定是一棵树。 $n$ 个点连通至少要 $n-1$ 条边；恰好 $n-1$ 条且连通的图就是树（第 01 讲）。如果你选了 $n$ 条边还连通，那就有环——环上随便删一条边仍然连通，而造价变小了。所以最优解不可能含环。
生成树：原图的一个子图，包含所有 $n$ 个点、恰好 $n-1$ 条边、且连通。 最小生成树（MST）：边权之和最小的生成树。
第二，暴力枚举没有希望。 完全图上生成树的个数是 $n^{n-2}$（Cayley 公式）。$n=10$ 就有 $10^8$ 棵，$n=20$ 是 $20^{18}$。必须用贪心。
而这里的贪心好用到有点反常：两个不同的贪心策略都对，而且都对得很彻底。
圈性质：图中任意一个环，环上权值最大的边（若唯一）一定不在任何 MST 里。
为什么：假设某棵 MST $T$ 包含了环 $C$ 上的最大边 $e$。把 $e$ 从 $T$ 里删掉，$T$ 断成两块，而 $e$ 的两个端点分别在两块里。环 $C$ 上除了 $e$ 还有另一条路把这两个端点连着，这条路上必有一条边 $f$ 横跨这两块（因为路从一块走到了另一块）。把 $f$ 加回来，又是一棵生成树，而 $w_f < w_e$——比 $T$ 更小，矛盾。
这就是 Kruskal 的全部依据：从小到大扫边，遇到”加进去会成环”的边就跳过。因为它是当前这个环上最大（或并列最大）的边。
割性质：把点集任意划分成两个非空部分 $S$ 和 $V\setminus S$，则横跨这个划分的所有边中，权值最小的那条（若唯一）一定在每棵 MST 里。
为什么：假设 MST $T$ 不含这条最小横跨边 $e=(u,v)$（$u\in S$、$v\notin S$）。$T$ 里 $u$ 到 $v$ 的那条唯一路径必然至少横跨一次，设那条横跨边是 $f$。把 $f$ 换成 $e$，仍是生成树，而 $w_e < w_f$——更小，矛盾。
这就是 Prim 的全部依据：维护一个已选点集 $S$，每次挑”从 $S$ 连出去的最短边”。