最小生成树 · Kruskal

最短路关注的是从一个点出发，到其他点怎么走最短。

最小生成树关注的是把所有点连成一张网络，总共选了多少边权。

Kruskal（克鲁斯卡尔）算法把问题拆成两件事：排序决定先考虑哪条边，并查集决定这条边能不能选。

本节以 Kruskal 为主线：从手推过程出发，理解贪心为什么正确，再把同一套代码迁移到连通块、瓶颈和虚拟点模型。Prim 只需先掌握核心思想与区别。

一、核心定义：我们到底要最小化什么？

1. 从“连通”走向“连通且代价最小”

给定一张包含 $n$ 个点、$m$ 条边的带权无向图，从原图中选出一些边，使所有点连通。

如果每条边都有建设成本，我们自然希望选出的总成本越小越好。

通俗理解： 并查集只能告诉我们“这些点现在连起来没有”；最小生成树还要回答“应该选哪些边，才能用最小的总代价连起来”。

先把问题限定在生成树上：选出的子图包含全部 $n$ 个点，并且连通、无环。

一棵有 $n$ 个点的树，恰好有 $n-1$ 条边。因此：

注意定义的边界： 当边权非负时，最小连通子图中可以删去环上的边而不增加成本，因此可以找到树形最优解。允许负权时，“任意连通子图的最小总权”与 MST 不一定相同：负权环可能值得全部保留。MST 始终要求选出的结构是一棵树。

2. 三个必须先说清的性质

• 原图不连通，就不存在生成树。 算法只能得到各个连通块的最小生成树，合起来叫最小生成森林。
• 最优总权值确定，但选边方案可能不唯一。 相同边权可能带来不同的最优选择；出现相同边权并不代表一定有多解。
• 负权边、零权边、重边都可以处理。 Kruskal 仍然按边权升序考虑；自环不能进入生成树。

当 $n=1$ 时，不选任何边就已经是一棵树，答案为 $0$。

3. 最小生成树不等于最短路树

考虑三条无向边：

• 最小生成树选择 $1-2$ 和 $2-3$，总权值是 $4$。但树上从 $1$ 到 $3$ 要走 $4$。
• 从 $1$ 出发的最短路树选择 $1-2$ 和 $1-3$，到 $3$ 只需走 $3$，但选边总权值是 $5$。

判断题意时先问：题目最小化的是路径长度，还是整张网络的选边总成本？

二、Kruskal 的起点：小边先选，但不能成环

1. 为什么不能直接取最小的 $n-1$ 条边？

因为最便宜的边可能集中在少数几个点之间：这些点已经绕成了环，其他点却还孤立着。

所以，“便宜”只决定考虑顺序，并不能代替合法性判断。

Kruskal 的完整规则是：

边权从小到大，端点异集合就选，同集合就跳过，成功选够 $n-1$ 条结束。

开始时，每个点单独构成一个连通块。每选入一条连接不同连通块的边，就把两个块合成一个块。

整个过程中维护的是一片森林，它可以暂时有多棵树，并不要求每一步都围绕同一个起点扩展。

2. 为什么“同一个集合”就代表加边会成环？

设当前考虑边 $(u,v,w)$。

• 如果 $u,v$ 已经连通，当前选中的边里就存在一条 $u$ 到 $v$ 的路径。再加入 $u-v$，这条路径与新边恰好闭合成环。
• 如果 $u,v$ 不连通，当前不存在这样的路径。加入新边只会连接两棵树，不会形成环。

因此，判环可以直接交给已经学过的并查集：

int fu=find(u),fv=find(v);
if(fu==fv) continue; // 已有路径，再加边就成环
// 否则可以选择这条边，并合并两个集合

这里检查的是连通性，不是路径长度。 已有路径的边权和完全可能大于当前边权。跳过这条边的理由是“成环”，不是“已经有更短的路”。

3. 为什么选够 $n-1$ 条就可以停止？

初始连通块数为 $n$，每次成功选边，连通块数恰好减 $1$。

当 cnt == n-1 时，只剩一个连通块。结合全过程无环，就已经得到一棵生成树。

计数器 cnt 记录的是成功选入的边数，不是已经扫描的边数。

三、手推一遍：排序、跳边与集合合并

给定 $5$ 个点、$7$ 条无向边，按权值排序后为：

初始集合：$\{1\},\{2\},\{3\},\{4\},\{5\}$。

此时 cnt == 5-1，直接结束，最小生成树总权值为 $12$。

这个例子要看懂三个地方：

1. 权值为 $3$ 的边虽然便宜，但会形成 $1-2-3-1$ 的环，必须跳过。
2. 选择 $4-5$ 时，它与前面选出的树还没有连接，仍然是合法操作。
3. 直接取排序后的前 $4$ 条边，总权虽然只有 $10$，却得到“一个环加一条边”，不是生成树。

四、贪心为什么正确：选了它，还能走向最优解吗？

1. 先分清两个问题

并查集只保证选出的边不成环，这是合法性。

按边权排序还必须保证结果总权最小，这是最优性。任意顺序加边也可能得到树，但未必得到最小生成树。

Kruskal 维护的关键性质是：

已经选中的所有边，可以同时包含在某一棵最小生成树中。

这句话意味着：每一次选择，都没有堵死走向最优解的道路。

2. 换边证明：给当前选择腾一个位置

假设当前已选边集合为 $F$，存在一棵包含 $F$ 的最小生成树 $T$。现在 Kruskal 准备选边 $e=(u,v,w)$。

取 $u$ 所在的当前连通块为 $S$，其余点为 $V\setminus S$。由于 $u,v$ 不连通，$e$ 跨越了这两个集合。

第一步：为什么 $e$ 是跨越这个划分的最轻边之一？

如果存在更轻的跨界边，它早已被扫描。当时它的两个端点也不可能连通，否则现在它们仍会处于同一个块。因此那条边应当已经被选入，与它现在仍然跨界矛盾。

第二步：如果 $T$ 已经包含 $e$，无需修改。

第三步：如果 $T$ 不包含 $e$，向 $T$ 中加入 $e$。

树上 $u$ 到 $v$ 原本有一条路径，加入 $e$ 后形成一个环。这条路径从 $S$ 走到外部，必然经过另一条跨界边 $f$。

由于 $e$ 是最轻跨界边之一：

删去 $f$，留下 $e$，就得到新树：

$T$ 已经最优，因此 $T'$ 也最优。而 $f$ 跨越当前连通块，不可能是 $F$ 中已经选中的边，所以原先的选择都被保留。

这就证明了：选入 $e$ 后，仍有一棵最小生成树包含所有已选边。 从空集开始反复执行，最后得到的整棵树就是最优解。

3. 切分定理与相等边权

把顶点划分为两个非空集合，称为一个割（切分）；两端分属两侧的边称为跨界边。

• 跨界边中任意一条最轻边，都属于某棵最小生成树。
• 如果它是该割上唯一最轻的边，那么它属于每棵最小生成树。

普通 Kruskal 求一棵 MST 时，相等边权可以任意排序，再逐条判环。上面的证明只需要 $\le$，不要求严格小于。

若题目改成“统计所有 MST”或“判断一条边是否出现在所有 MST 中”，相同权值的处理需要进一步分析，不能直接照搬一次选边结果。

五、标准模板：排序与并查集各司其职

1. 变量含义与存图方式

Kruskal 按边扫描，无需查找某个点的所有邻居，所以使用边集数组即可。输入一条无向边，就存一条记录，不必反向再存一次。

下面沿用讲义中的 #define int long long、1-based 下标和 solve() 封装。按大小合并与路径压缩配合使用，保证并查集操作的均摊复杂度。

2. 完整代码

输入格式为 n,m 和接下来的 $m$ 条 u,v,w。无解输出 orz，与 P3366 【模板】最小生成树 一致。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=100005;
const int M=200005;

struct Edge{
    int u,v,w;
    bool operator<(const Edge& x)const{
        return w<x.w; // 必须严格小于，不能写 <=
    }
}edge[M];

int n,m,fa[N],sz[N];
int ans,cnt;

void init(){
    for(int i=1;i<=n;i++){
        fa[i]=i;
        sz[i]=1;
    }
}

int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

// 返回值表示：是否真的把两个不同集合合并了
bool merge(int u,int v){
    int fu=find(u),fv=find(v);
    if(fu==fv) return false;
    if(sz[fu]<sz[fv]) swap(fu,fv);
    fa[fv]=fu; // 小集合挂到大集合上
    sz[fu]+=sz[fv];
    return true;
}

bool kruskal(){
    init();
    sort(edge+1,edge+1+m);
    ans=cnt=0;

    for(int i=1;i<=m&&cnt<n-1;i++){
        if(!merge(edge[i].u,edge[i].v)) continue;
        ans+=edge[i].w;
        cnt++;
    }
    return cnt==n-1;
}

void solve(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>edge[i].u>>edge[i].v>>edge[i].w;
    }
    if(kruskal()) cout<<ans<<'\n';
    else cout<<"orz\n";
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    solve();
    return 0;
}

3. 复杂度分析

• 初始化并查集：$O(n)$。
• 排序：$O(m\log m)$。
• 扫描边，配合路径压缩与按大小合并：$O(m\alpha(n))$。
• 总时间为 $O(n+m\log m+m\alpha(n))$，通常记作 $O(n+m\log m)$；在连通图的常规分析中简写为 $O(m\log m)$。
• 空间复杂度：$O(n+m)$。

其中 $\alpha(n)$ 为反阿克曼函数，在竞赛数据规模下增长极慢。主要耗时通常来自边排序。

4. 并查集的树，不是最小生成树！

执行 fa[fv]=fu 只是合并集合代表；fu,fv 之间未必存在原图边。路径压缩还会继续改变 fa 的形态。

如果后续要在 MST 上做 DFS、倍增或树形 DP，必须在成功选边的位置，额外记录当前原图边：

// tree 定义为 vector<pair<int,int>> tree[N];
if(merge(u,v)){
    ans+=w;
    cnt++;
    tree[u].push_back({v,w});
    tree[v].push_back({u,w});
}

集合关系看 fa，实际选出的树边看 tree，两者不能混用。

六、Kruskal 的模型迁移：改变停止条件与答案含义

1. 已经连好的部分：先合并，再选边

模型： 一些点之间已经免费连通，现在只计算新增连接的最小成本。候选连接成本非负。

先初始化并查集，把已有连接全部合并。维护当前连通块数 blocks，只有真正合并两个不同集合时才减一：

init();
int blocks=n;
// 对每条已有连接 (u,v)：
if(merge(u,v)) blocks--;

再按边权扫描候选边，每次成功合并都累加新费用并执行 blocks--，直到 blocks==1。

易错点： 已有边可能重复、可能成环，不能直接用“$n$ 减去已有边条数”计算连通块数。

2. 恰好保留 $k$ 个连通块：选够 $n-k$ 条边

模型： 从 $n$ 个孤立点开始，选出一片包含全部点、恰好有 $k$ 个连通块的森林，使总边权最小。

仍然按 Kruskal 贪心选择，每次成功合并减少一个块，因此目标选边数变为：

把模板中的停止条件和成功条件从 n-1 改成 n-k 即可。

• 当 $k=n$ 时，一条边也不用选，答案为 $0$。
• 若原图最终有 $c$ 个连通块，当 $c>k$ 时无法完成目标。
• 这里最小化的是森林总权值；若题目要求“不同组之间的最小距离最大”，答案含义不同，不能直接输出这里的 ans。

对应练习：P1195 口袋的天空。

3. 瓶颈模型：让选中边的最大值尽可能小

模型： 连通全部点，最小化所选生成树中的最大边权。

Kruskal 按升序选边，最后一条成功选入的边权记为 $W$，它就是这棵 MST 的最大边权。

为什么 $W$ 已经最小？

只使用边权严格小于 $W$ 的边时，原图还没有连通，否则算法早就能完成。于是任何生成树都至少需要一条权值不小于 $W$ 的边。而 Kruskal 用不超过 $W$ 的边完成了连通，所以答案恰好为 $W$。

这也说明：最小生成树一定是最小瓶颈生成树，反过来不一定。

例如三条边权为 $1,2,2$ 的三角形：选 $1+2$ 与选 $2+2$，瓶颈都为 $2$，但只有前者总权最小。

代码中在成功选边时执行 last=w，完成连通后输出 last。若只有一个点，则没有最大边，按题目约定处理，常见约定是输出 $0$。

对应练习：P1547 [USACO05MAR] Out of Hay S。

4. 虚拟点建模：把“单独购买”也变成一条边

模型： 每件物品可以按原价单独购买；已经买到某件物品后，可以按给定的对称优惠价购买另一件。费用非负，求买齐的最小总成本。

把物品当作点，优惠关系当作边。但“单独买下一个物品”没有对应的另一端，怎么放进图里？

增加虚拟点 $0$：

• 从 $0$ 向物品 $i$ 连边，边权为原价，表示单独购买。
• 物品之间连优惠边，表示在已购入一件的基础上购买另一件。

这样，所有物品最终与 $0$ 连通，就代表都能购入。把生成树以 $0$ 为根，按父亲先于孩子的顺序购买，即可实现树上的总成本。

新图有 $n+1$ 个点，因此需要成功选入 $n$ 条边。并查集初始化范围也要包含 $0$ 号点。

对应练习：P1194 买礼物。本题矩阵中的 $0$ 表示没有优惠关系，不能当作免费边；原价边仍应正常加入。

七、Prim 简介：从一个点逐步长成一棵树

1. 核心思想

Kruskal 允许多个连通块同时存在；Prim 始终维护一棵正在生长的树。

设已经加入树的点集为 $S$：

1. 从任意一点开始。
2. 在一端属于 $S$、另一端不属于 $S$ 的边中，选一条最轻边。
3. 加入这条边和它在外部的端点。
4. 重复，直到加入全部点；若找不到跨界边却仍有未加入的点，说明原图不连通。

每次都是选割上的最轻边，因此仍由切分定理保证正确性。

2. dis[v] 表示什么？

对于未加入的点 $v$：

它表示用一条边把 $v$ 接到当前树上的最小代价，不存在这样的边则为无穷大。

新点 $u$ 加入后，用它的邻边更新：

dis[v]=min(dis[v],w); // w 是边 (u,v) 的权值

Prim 接进来一个点，只支付它与当前树之间的那一条边，不把到某个起点的路径再付一遍。

3. 朴素 Prim 的核心轮廓

以下是算法轮廓，g[u][v] 表示邻接矩阵边权，无边为 INF，重边取最小值。

dis 全部设为 INF，vis 全部设为 false
dis[1] = 0，ans = 0
重复 n 次：
    找未加入的点中 dis 最小的点 u
    如果 dis[u] == INF：原图不连通，结束
    vis[u] = true
    ans += dis[u]
    枚举所有未加入的点 v：
        dis[v] = min(dis[v], g[u][v])

起点的 dis[1]=0 表示它不需要通过一条边接入，不是在原图中增加了一条零权边。

朴素 Prim 时间为 $O(n^2)$，邻接矩阵空间为 $O(n^2)$，适合点数不大、边非常多的稠密图；若边权能直接计算，也可以按需计算而不存完整矩阵。

堆优化 Prim 可以用于稀疏图。本节先理解上述轮廓，主要上机任务仍是 Kruskal 的实现与变形。

八、易错点：代码很短，含义必须明确

1. 并查集应当维护已选边的连通关系。 普通 MST 不能一读入边就全部合并，否则开始选择时所有点可能已经同集。
2. 判同集必须调用 find。 fa[u]==fa[v] 只比较直接父亲，不等价于同属一个集合。
3. 只在合并成功时更新 ans 和 cnt。 重边、自环以及其他成环边都会被跳过。
4. 结束后检查 cnt。 图不连通时累加的是森林权值，不能把它当成 MST 答案。
5. 总权值使用 64 位整数。 本文沿用全局宏，也可以只把边权和答案声明为 long long；不是必须使用宏。
6. 排序比较器写 <，不能写 <=。 相等元素也返回真会破坏比较器要求。
7. 数组容量按题目上限留余量。 本文使用 1-based，数组容量必须大于最大有效下标；虚拟点模型还需调整点数、边数与初始化范围。
8. 若要求输出具体边，保留原始编号。 排序后的数组下标已经不是输入顺序。

九、MST 进阶：非树边替换与严格次小生成树（选学）

先修说明：本节需要熟练掌握“最近公共祖先 (LCA)”与“树上倍增算法”，可先读《树上路径处理》第二节。若尚未学习，可先跳过，不影响基础图论做题。

当我们求出一棵最小生成树 (MST) 后，原图中的边就被分成了两类：树边（共 $n-1$ 条）和非树边。

如果我们强行把一条非树边 $(u, v, w)$ 塞进这棵树里，会发生什么？ 这就像在一张已经连通的网络里强行拉一条新网线，必然会和原有的树边一起构成一个环。

为了让它重新变回一棵树，我们必须在这个环上“砍”掉一条原来的树边。这个过程，就叫作非树边的替换。

1. 替换代价的物理意义

为了让替换后的新树总权值尽可能小，我们应该砍掉哪条边？当然是环上权值最大的那条树边！

假设 $u$ 到 $v$ 在原 MST 上的路径最大边权为 $w_{max}$，加入新边 $w$ 并删去 $w_{max}$ 后：

2. 次小生成树与“严格”的陷阱

次小生成树：总权值排名第二的生成树。它可以通过枚举每一条非树边，计算替换代价，取代价最小的方案得到。

但题目常常会考严格次小生成树，即新权值必须严格大于 $W_{mst}$。 这里有一个巨大的陷阱：如果非树边 $w$ 恰好等于路径最大边 $w_{max}$ 呢？ 此时替换代价为 $0$，新树的总权值依然是 $W_{mst}$。这只是找到了另一棵最小生成树，而不是“严格次小”。

破局思路：区分最大值与严格次大值 当 $w == w_{max}$ 时，我们不能替换最大边，只能退而求其次，去替换路径上的严格次大边 $w_{cmax}$ （且 $w_{cmax} < w_{max}$）。 这样替换的代价变成了 $(w - w_{cmax})$，由于 $w = w_{max} > w_{cmax}$，这个代价绝对大于 $0$，完美满足严格递增的要求！

所以，在树上倍增维护 LCA 的过程中，我们不仅要维护区间最大边 mx1，还必须维护严格次大边 mx2。

3. 代码实现：树上倍增维护最大与次大

下面的完整程序展示了如何通过一次 Kruskal 建树，再用树上倍增寻找严格次小生成树。这里假设原图连通，而且严格次小生成树存在；若题目不保证存在，要在输出前判断 ans2 是否仍为 INF，按题面要求处理。

自拟验证样例： 输入 4 个点 5 条边：

4 5
1 2 1
2 3 2
3 4 3
4 1 4
1 3 3

MST 选边 1-2(1), 2-3(2), 3-4(3)，总和 6。 非树边 4-1(4)，树上 4 到 1 路径最大边为 3，替换代价 4-3=1，新树权值 7。 非树边 1-3(3)，树上 1 到 3 路径最大边为 2，替换代价 3-2=1，新树权值 7。 严格次小生成树权值为 7。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=100005, M=300005, INF=1e18;

struct Edge {
    int u, v, w, id; 
    bool operator<(const Edge& x) const { return w < x.w; }
} edge[M];

int n, m, dsu[N];
bool used[M]; // 通过边编号标记哪些边成为了树边
vector<pair<int,int>> tree[N];

int find(int x) { return dsu[x]==x ? x : dsu[x]=find(dsu[x]); }

// 倍增数组：2^i 祖先、最大边、严格次大边
int fa[N][20], dep[N], mx1[N][20], mx2[N][20];

void dfs(int u, int p, int w_up) {
    fa[u][0] = p;
    dep[u] = dep[p] + 1;
    mx1[u][0] = w_up;
    mx2[u][0] = -INF;

    for(int i=1; i<=18; i++) {
        fa[u][i] = fa[fa[u][i-1]][i-1];
        int m1 = mx1[u][i-1], m2 = mx2[u][i-1];
        int v1 = mx1[fa[u][i-1]][i-1], v2 = mx2[fa[u][i-1]][i-1];
        
        // 合并求出 2^i 路径上的最大值和严格次大值
        mx1[u][i] = max(m1, v1);
        mx2[u][i] = -INF;
        if(m1 != mx1[u][i]) mx2[u][i] = max(mx2[u][i], m1);
        if(m2 != mx1[u][i]) mx2[u][i] = max(mx2[u][i], m2);
        if(v1 != mx1[u][i]) mx2[u][i] = max(mx2[u][i], v1);
        if(v2 != mx1[u][i]) mx2[u][i] = max(mx2[u][i], v2);
    }

    for(auto ed : tree[u]) {
        int v = ed.first, w = ed.second;
        if(v != p) dfs(v, u, w);
    }
}

// 查询 u 到 v 路径上，严格小于 w 的最大边权
int qmax(int u, int v, int w) {
    int res = -INF;
    if(dep[u] < dep[v]) swap(u, v);
    for(int i=18; i>=0; i--) {
        if(dep[fa[u][i]] >= dep[v]) {
            if(mx1[u][i] == w) res = max(res, mx2[u][i]);
            else res = max(res, mx1[u][i]);
            u = fa[u][i];
        }
    }
    if(u == v) return res;
    for(int i=18; i>=0; i--) {
        if(fa[u][i] != fa[v][i]) {
            if(mx1[u][i] == w) res = max(res, mx2[u][i]);
            else res = max(res, mx1[u][i]);
            
            if(mx1[v][i] == w) res = max(res, mx2[v][i]);
            else res = max(res, mx1[v][i]);
            
            u = fa[u][i]; v = fa[v][i];
        }
    }
    if(mx1[u][0] == w) res = max(res, mx2[u][0]);
    else res = max(res, mx1[u][0]);
    
    if(mx1[v][0] == w) res = max(res, mx2[v][0]);
    else res = max(res, mx1[v][0]);
    
    return res;
}

void solve() {
    cin >> n >> m;
    for(int i=1; i<=m; i++) {
        cin >> edge[i].u >> edge[i].v >> edge[i].w;
        edge[i].id = i; // 记录原始编号
    }
    sort(edge+1, edge+1+m);
    
    for(int i=1; i<=n; i++) dsu[i] = i;
    
    int sum_mst = 0, cnt = 0;
    for(int i=1; i<=m; i++) {
        int u = edge[i].u, v = edge[i].v, w = edge[i].w, id = edge[i].id;
        int fu = find(u), fv = find(v);
        if(fu != fv) {
            dsu[fv] = fu;
            sum_mst += w;
            cnt++;
            used[id] = true; // 边编号 id 成为了树边
            tree[u].push_back({v, w});
            tree[v].push_back({u, w});
        }
    }
    
    if(cnt < n-1) { cout << "orz\n"; return; }
    
    dfs(1, 0, -INF);
    
    int ans2 = INF;
    for(int i=1; i<=m; i++) {
        if(!used[edge[i].id]) {
            int val = qmax(edge[i].u, edge[i].v, edge[i].w);
            if(val != -INF) {
                ans2 = min(ans2, sum_mst - val + edge[i].w);
            }
        }
    }
    cout << ans2 << '\n';
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}

十、MST 进阶：判断 MST 的唯一性（选学）

题目有时会问：“最小生成树是否唯一？” 通过刚才的替换代价理论，我们很容易得出：如果存在一条非树边，它的权值 $w$ 恰好等于树上对应路径的最大边 $w_{max}$，那么它们可以无损互换，MST 就不唯一。

1. 为什么要用边编号区分重边？

在判断相等互换时，有一个必须小心的细节：图中可能有两点之间权值相同的多条连线（重边）。

例如，节点 $A$ 和 $B$ 之间有两条权值都为 $5$ 的边。 在 Kruskal 中，第一条 $5$ 号边加进去了成为了树边；遍历到第二条 $5$ 号边时，并查集发现已经连通，于是它成了非树边。

当我们用这条非树边去对比树上路径时，路径最大边 $w_{max}$ 显然也是 $5$。$w == w_{max}$，可以互换，意味着我们换了一条物理上不同的边，方案确实变了，MST 不唯一。

但如果代码写得不严谨，直接遍历邻接表去比对权值，就有可能把一条树边自己和自己比对。 为了精准防止“同自己替换”，我们必须给最初输入的每一条边打上唯一的 id 标签（如上一节代码中的 edge[i].id）。

2. 判断唯一性的简单流程

1. 跑一遍 Kruskal，把选取的边用 used[id] = true 记录下来。
2. DFS 预处理树上倍增，但不强制求严格次大，只需要路径最大边 mx1 即可。
3. 枚举所有 used[id] == false 的非树边，查询树上路径最大值 val。
4. 如果发现某条边满足 edge.w == val，则立刻判定：MST 不唯一。

这里要查询的是路径最大边本身，不能直接复用上一节只返回“严格小于 w 的最大边权”的 qmax，否则会漏掉等权替换。

这套依靠边编号 (id) 加上树上最大值替换的打法，需要树上倍增；不使用 LCA 的同权分组判法，见《最小生成树 (MST)：建模与算法选型》第四节第 5 小节。两种方法都要区分重边的身份与同权替换。

十一、渐进式实战练习题单

1. 基础模板与停止条件

1. P3366 【模板】最小生成树
   • 考点：边排序、并查集判环、无解判定。
   • 要求：独立写出完整 Kruskal，并解释 cnt==n-1 的含义。无解输出 orz。
2. P1195 口袋的天空
   • 考点：从生成树迁移到恰好 $k$ 个连通块。
   • 思路：把目标选边数改为 $n-k$，不足时输出 No Answer。特别检查 $k=n$。

2. 答案含义与建图转化

3. P1547 [USACO05MAR] Out of Hay S
   • 考点：MST 中的最大边权。
   • 思路：记录最后一次成功合并的边权；能用“低于这个阈值还不能连通”解释最优性。
4. P1194 买礼物
   • 考点：虚拟点、原价边与优惠边。
   • 思路：新增 $0$ 号点后跑 MST，注意优惠矩阵中 $0$ 的特殊含义。

3. 课堂自检

• 为什么排序后不能直接取前 $n-1$ 条边？
• 为什么两端同集就要跳过，而不需要比较已有路径的长度？
• 为什么 Kruskal 可以先选出几棵互不相连的树？
• fa 数组能否直接拿来做最小生成树上的 DFS？
• 把 Prim 的更新写成 dis[u]+w，改变了哪个量的含义？

能解释这些问题，再独立完成模板与一种变形，才算真正掌握这一节。