最小生成树：Kruskal 与 Prim

• 生成：所有 n 个点都得连上（不是「连上一部分」）；
• 树：恰好 n−1 条边、不成环。

这两条其实是一件事的两面：n 个点、n−1 条边、连通 ⇔ 是一棵树。 所以代码里只要盯住一个数字：选中的边数有没有到 n−1。 到不了，就说明图本来不连通 —— 第 9 步那个错误版本漏的就是这一句。

6 10
1 2 1      ┐
2 3 1      ├ 左边一个三角 1-2-3，★ 其中 1—3 是 -2（负权边）
1 3 -2     ┘
3 4 5      ← 桥一
4 5 2      ┐
5 6 3      ├ 右边一个三角 4-5-6
4 6 4      ┘
2 4 5      ← 桥二，★ 和桥一**权值并列**（都是 5）
1 1 -7     ← ★ 一条**负的自环**
3 4 9      ← ★ 3—4 的**重边**（更贵的那条）

手算（把边从小到大排一遍，能连就连）：

答案 9（= −2+1+2+3+5）。

★ 那条 −7 的自环是这张图的第一个陷阱：它是全图最小的边，可它一个新点都连不上， 那点「白送的负权」根本拿不到。第 9 步有一份代码就栽在这儿。

⚠ 顺带对照一下第 33 章：那一章一条负的自环就是一个负环，是灾难； 这一章它完全无害。同一样东西在两道题里的分量可以差得非常远。

6 7
1 2 1
2 3 1
1 3 -2
4 5 2
5 6 3
4 6 4
1 1 -7

左边一块、右边一块，中间一条边都没有。答案：IMPOSSIBLE。

⚠ 但请注意：Kruskal 在这张图上照样跑得欢 —— 它长出来的是一片 最小生成森林（每块各一棵，权值和 4）。不崩溃、不越界、数还挺像话。 第 9 步那个错误版本报的就是这个 4。

Kruskal 和 Prim 都是贪心，而且是同一条性质的两个推论。 拿它们互相验，只能验出「两处打字错误不一样」，验不出「那条性质本身是不是被我理解错了」。

所以这一份直接照着定义做：生成树 = 选 n−1 条边 + 所有点连通， 把 2^m 个子集全枚举一遍，合法的里面取最小。

第 9 章用 DP 验贪心、第 15 章用迭代加深验 BFS —— ★ 标准答案要用完全不同的思路写，同一个思路写两遍只能验出打字错误。

而「一个集合就是一个整数」也是第三次登场了：第 3 章拿它当枚举手段， 第 28 章升级成状态，这里又变回枚举手段 —— 只不过枚举的是边。

把 n 个点任意分成两半：S 和 V∖S（这就叫一个切割）。 一端在 S、另一端在 V∖S 的边，叫横跨这个切割的边。

★ 横跨它的边里最小的那一条 e，一定属于某一棵最小生成树。

证明只有三句话，而且是第 19 章那个交换论证的原样重演：

1. 随便拿一棵最小生成树 T。如果 e 已经在里面，收工。
2. 如果不在：把 e 加进 T，n 个点 n 条边必定出现一个环。 这个环从 S 出去、又回到 S，所以环上至少还有另一条横跨切割的边 f。
3. 而 e 是横跨的边里最小的，所以 w(e) ≤ w(f)。 把 f 换成 e，还是一棵生成树，权值和 ≤ 原来 —— T 已经是最小的了， 所以新的这棵也是最小的，而它含 e。∎

⚠ 请数一数这三句话里用到了什么：加进去会成环（图论）、环上必有第二条横跨边（数数）、 w(e) ≤ w(f)（e 是最小的）。

★★ 「边权非负」一次都没有出现。

第 32 章证明 Dijkstra 时，反证的第三句是「后面那一段路的长度 ≥ 0，所以绕远只会更远」—— 「边长非负」恰好用在那一个不等号上，负权一来，那句话就断了，反例就长在那儿。

这一章的三句反证里没有那个位置可断。所以：

★ 第 20 章那句「证明断在哪一步，反例就长在哪里」，这一章给出的是它的反面： 证明里压根没用到的条件，放开它也不会有反例。 所以这一章的对拍数据里必须有负权边 —— 它验的就是这句话。

⚠ 但要说准：不怕负权 ≠ 什么都不怕。负的自环照样拿不到（第 2 步那条 −7）， 因为「树」那个限制还在。

★ 所以这一章不是「两个算法」，是一条性质 + 两种挑切割的方式。 Kruskal 到处开花（一堆连通块慢慢并成一棵），Prim 只有一棵树、一直在长。

把写法切成「✗ 写成 Dijkstra（key[v] = key[u] + w）」，它立刻变成 1 次： 那一份比的不是「那条边本身」，而是「从 1 号一路走过来的总长」， 于是它选的边不是横跨切割里最小的那条。

⚠ 请把这个画面和第 32 章那个 DijkstraProof 摆在一起看 —— 两个动画的形状是一样的（每一步都暴力枚举、当场对质），结论正好相反：

这就是第 4 步那张表的画面版：差别不在代码里，在证明里。

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }   // 一路往上找祖宗，顺手压缩

bool unite(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return false;      // 本来就连通 —— 再连就成环
    fa[a] = b;                     // ⚠ 接的是两个**祖宗**
    return true;
}

路径压缩就是 fa[x] = find(fa[x]) 那半句：回来的路上，把这一路的点 全部直接挂到祖宗身上，下次一步到位。 （它为什么快到「几乎 O(1)」，第 36 章会算给你看 —— 这一章只用它。）

★ 用它之后，「自环」和「重边」根本不用特殊处理： 自环两端本来同族，find 一比就自己跳过了；重边里更小的那条先被收下， 更大的那条之后自然成环。第 29 章那两个必须小心的东西，在这里是白送的。

点「运行 ▶」看结果

图 A 上它给 22（正解 9）。而它不是「随机地错」——

点「运行 ▶」看结果

也是 22。而且 300 组随机数据，一组不差（钉在 check:viz 里）。

★ 排序反了 ≡ 最大生成树。 这是本教材第十条这样的恒等式 （前九条在第 23、24、25、26、27、28 章）。 ⚠ 验法照旧讲究：两份程序思路必须不同（一份 Kruskal、一份 Prim）， 否则只是把同一个错抄了两遍。

顺带一句：最大生成树也是切割性质的推论 —— 把三句反证里的「最小」全换成「最大」， 一个字都不用改。贪心的方向可以反过来，性质的形状不变。

// 第 32 章 naive.cpp（朴素 Dijkstra）
if (dist[u] + g[u][v] < dist[v]) dist[v] = dist[u] + g[u][v];

// 这一章 prim.cpp
if (          g[u][v] < key[v] ) key[v]  =           g[u][v];
//      ↑ 少了「dist[u] +」这一截

一句话解释这个差别：

★ 而这正好解释了第 4 步那张表：Dijkstra 要累加，所以它的贪心需要「路越走越长」； Prim 压根不累加，切割性质的证明里一次都没用到 w ≥ 0。

第 33 章说「SPFA 就是第 32 章那份堆优化，只差用什么容器」； 这一章说的是另一半：★ 容器可以一模一样，差的是往 key 里放什么。

它算出来的是最短路径树：从 1 号出发，每个点都用「最短路」连过来。 那是一棵完全合法的生成树 —— 只是通常不是最小的那棵。

★ 「它给了一棵合法的树」和「它给了最小的那棵」是两件事。 第 32 章那句「它给了对的答案 ≠ 这个算法成立」的同一个形状。

⚠ 写这个错误版本时我特意补了一句 g[u][v] < INF 的守卫。不补的话， 有负权时 key[u] + INF 会比 INF 小，「够不着」也被刷成一个数 —— 那正是第 33 章 wrongInf.cpp 那个坑。★ 错误版本也要干净：一份只错一件事， 否则量出来的抓获率说不清是谁的功劳。

点「运行 ▶」看结果

// 第 32 章 fast.cpp                        这一份
if (d + w < dist[v]) {                     if (!in[v] && w < key[v]) {
    dist[v] = d + w;                           key[v] = w;          // ★ 就是这一个字
    q.push({dist[v], v});                      q.push({key[v], v});
}                                          }

⚠ 判重那一句这里用 if (in[u]) continue; 而不是照抄 if (d > key[u]) continue; —— 两种写法在这道题上都对，但 in[] 说的正是「已经进树的点不能再进第二次」， 和朴素版里那个 in[] 是同一个东西。 （第 33 章那条：这个标记到底在记什么，比它叫什么重要一百倍。）

错在把题目看成了「权值最小」四个字，漏掉了前半句：必须恰好是一棵树。 负权边照样会凑成环，凑成环就不能全要。

而图 A 上最刺眼的是那条 −7 的自环：它是全图最小的边， 可它一个新点都连不上 —— 那点白送的负权，你拿不到。

⚠ 这个 bug 对生成器提出了一个非常具体的要求：数据里得有负权边凑出来的环， 最好还有负的自环。全是正权的数据上它和正解一模一样（第 11 步那张表：档位 0/1 都是 0）。

第 31 章（拓扑排序）是本教材第一次碰到「答案不唯一」，当时给了两条出路：

① 把答案钉唯一。 第 31 章是靠给题面加一句「输出字典序最小的那个」硬钉的； 这一章白送 —— 这道题天生就有一个唯一的东西：权值和。 所以题面只要那一个数，主对拍就能逐字节比。

★ 「答案不唯一」时的第一个动作，是先找找有没有一个天生唯一的量 —— 有的话，题面就该只要它。

② 写验证器。 不比答案，比性质。check:viz 拿到 plan.cpp 那两棵树，各查四件事：

300 组数据、每组两棵树，全部通过。

⚠ 第 31 章那个盲区在这里还在：验证器证明不了「答案存在时你没漏报」 —— 一份永远输出 IMPOSSIBLE 的程序能通过上面每一条检查。 所以「不连通」那一支必须靠主对拍单独对。 （第 20 章「对拍只能证伪」、第 31 章「验证器的盲区」、第 33 章「随机数据碰不到最坏情况」—— 这是随机对拍的第二个盲区在这一章的复现。）

★ 还有一个细节值得记：前四条里，前三条能自证清白，第四条不能。 「它是不是一棵合法的生成树」验证器自己就能查完； 「它是不是最小的那棵」只能靠那个数字，也就是靠 brute.cpp。 第 27、28 章那句「一份方案能自证清白，一个数字不能」，在这一章要反过来用一半。

gen.cpp 带了九个档位（./gen 种子 档位），种子固定 1..300：

★ 档位 1 那一行是这一章最刺眼的地方，而且它是「双向」的： 「忘了判够」从 0 一下子变成 224（这一支终于有了）， 可别的三个 bug 全被腰斩（210→48、201→104、120→28）—— 因为一旦图不连通，所有程序一律输出 IMPOSSIBLE，别的 bug 连出场机会都没有。

⚠ 第 31、33 章那条「某一支占得太多，会把别人挤没」的第四次。 这次占到了 224 / 300（七成半），比第 31 章那次还狠。

⚠ 另外两笔老实账：

• 档位 2 只把「负边全收」从 0 抬到 9。 光有负权边不够 —— 它要的是负边凑成的环。 档位 3 一放开自环和重边，才跳到 33（★ 大头是负的自环，第 29 章那条兑现）。 「加了个好东西」不等于「数据变好了」（第 33 章那条的第二次）。
• 档位 4（打乱编号）五个数字几乎一个没动（60/91/224/33/20 对比档位 3 的 60/92/224/33/19）。 而第 27、31、32 章里同样一处改动是决定性的（0 / 300 → 两百多）。下一张表会说清为什么。

★ 档位 7 是这一章最值得说的一档：它是一次撤回。

档位 5 那处「把边权值域拉开」，在当时（八成的组都不连通）看着是有效的 （不 find 从 92 涨到 104）。可等档位 6 把不连通降下来之后再对照一量： 五个 bug 的抓获率几乎一个数都没变（191/169/69/109/66 → 191/165/69/107/67）， 而它还有一个副作用 —— 值域一宽，并列的边权就少了， 「两棵最小生成树长得不一样」的组数从 10 掉到 1。 而「答案不唯一」正是这一章的第二个主题。于是这处改动被撤回了。

★ 第 32 章那条「调优不可加：一处改动值不值得留，取决于其它旋钮此刻在哪」的第二次， 而且这一次的结论是减法。 别把调生成器当成「把好点子一条条加上去」 —— 有的点子后来是要拿掉的。

★ 档位 8 那个对照回答了上一张表留下的问题：为什么「打乱编号」在这一章这么弱？

⚠ 所以「顺手写法会悄悄给数据加一条题目里没有的性质」这条规律，要补一句： ★ 它危不危险，取决于题目在问什么。 这和第 33 章那条「同一句代码危不危险，取决于数据的取值范围」是一对。

（它最后还是留下了：定档标准照旧是第 32 章那条 —— 让最弱的那一支尽量强， 档位 8 最弱的是 59，档位 7 是 67。而且退化数据防的是还没写出来的 bug， 第 27 章档位 3 那笔账的同款。）

⚠ 朴素 Prim 那个 O(n²) 空间是最容易被忽略的一栏，而它往往先出事 —— 邻接矩阵要 4(n+1)² 字节，这正是第 29 章那个公式。

光看后三列，结论是「三者差不多」（0.37 / 0.77 / 0.40）。 可读入本身就吃掉了 0.34 秒 —— 减掉它之后：

★ 算法部分差了十四倍，而不是「差不多」。 ./count io 这个开关就是为这件事加的（count.cpp）。

★ 第 29 章那条「量之前先确认「你量的就是它」」的第三次 （第一次是量内存时把去重的 set 也量进去了，第二次是第 32 章两份代码 I/O 设置不一致）。 这一次的教训更直白：稠密图的输入本身就是主要开销，不单独量出来， 你比的就不是算法，是 cin。

⚠ 顺带：这一次那句口诀（「稠密图该用朴素 Prim」）终于复现出来了 —— 第 29、32、33 章连着三次都没复现出各自那句口诀，这是第一次量到相符的。 口诀不是都错，是都得量。

★ 一句话：先看图稀不稀疏。 稀疏（m ≈ n）用 Kruskal； 稠密（m ≈ n²）且 n 只有几千，朴素 Prim 反而最快 —— 但先确认 4(n+1)² 的内存开得出来。

【1】★ 切割性质：横跨任意切割的最小边，一定在某棵最小生成树里。 三句反证（加进去成环 → 环上必有第二条横跨边 → 换掉它不会更差），就是第 19 章那个交换论证。 Kruskal 和 Prim 都是它的推论，只是选的切割不一样： Kruskal 用「这条边左端所在的连通块」，Prim 用「已经长进树里的那堆点」。

【2】★ 那三句话里「边权非负」一次都没出现 —— 所以这一章的贪心不怕负权。 对照第 32 章：Dijkstra 的反证里非负性恰好用在一个不等号上，负权一来就断。

★ 第 20 章「证明断在哪一步，反例就长在哪里」的反面： 证明里压根没用到的条件，放开它也不会有反例。 ⚠ 但「不怕负权」≠「什么都不怕」：负的自环照样拿不到，因为「树」那个限制还在。

【3】★ Prim 和 Dijkstra 只差一截「dist[u] +」。 dist[v] 记的是「从起点走到 v 多远」（要累加），key[v] 记的是「从树上够到 v 多少钱」（只看一条边）。 写混了就得到最短路径树 —— 一棵合法的、但通常不是最小的生成树。

★ 「它给了一棵合法的树」和「它给了最小的那棵」是两件事。

【4】★ 答案不唯一时，先找有没有一个「天生唯一」的量。 最小生成树可能不止一棵，但权值和唯一 —— 于是题面只要那个数，主对拍就能逐字节比 （第 31 章是靠加一句「字典序最小」硬钉的，这一章白送）。 方案本身交给验证器（n−1 条边 + 都在原图里 + 连通 + 权值和对得上）。 ⚠ 验证器的盲区还在：它证明不了「答案存在时你没漏报」。

【5】★ 调生成器有时候要做减法。 这一章那个「拉开边权值域」的改动，加的时候有效、环境变了之后就没用了，还有害 （并列权值一少，「两棵树不同」从 10 掉到 1），最后被撤回。

★ 第 32 章「调优不可加」的第二次，而这次结论是减法。 同一件事的另一面：「顺手写法」危不危险，取决于题目在问什么 —— 打乱编号在第 27、31、32 章是 0 → 两百多，在这一章几乎没动， 因为这一章问的是一个和编号无关的数。