最小生成树

定义¶

生成树 是 无向连通图 的一个子图，它包含原图中的所有结点，并且是一棵树（即没有环）。
如果一个无向连通图有 $n$ 个点，则其生成树恰好有 $n-1$ 条边。
可以通过 删去图中的若干条边，直到图变成一个不含环的连通子图，即生成树。

在所有可能的生成树中，边权之和最小 的那一棵生成树，就称为 最小生成树（Minimum Spanning Tree，MST）。

注意：只有连通图才有生成树，而对于非连通图，只存在生成森林。

要找出一棵边权和最小的生成树，常见有两种经典算法：

Prim 算法：从一个点开始，不断扩展最近的点，像水波一样向外蔓延。
Kruskal 算法：把所有边从小到大排个队，一根一根挑选，尽量避免形成环。

Prim 算法¶

基本思想¶

从一个结点出发，逐步向外扩展，每次选择距离当前生成树集合最近的一个点加入。
过程类似于 Dijkstra 最短路算法，也可使用堆优化。

算法本质¶

每次扩展的是 当前生成树到外部点的最短边，而不是整张图的最短路径。
因此 Prim 算法是一个加点的过程，而非松弛路径。

算法流程¶

初始化

将所有结点分为两类：
- $S$：已加入生成树的点
- $T$：未加入生成树的点
从任意一个点（如 $1$ 号点）开始，加入 $S$，其 $dist = 0$，其余点的 $dist = \infty$

主循环

在 $T$ 中找到 $dist$ 最小的点 $u$，加入 $S$
用 $u$ 去更新其他未加入点 $v$ 的 $dist$：

\[ dist_v = \min(dist_v, w(u,v)) \]

注意：不需要加上原点距离，只关注最短边权

记录结果

每加入一条边，累加其边权，最终得到 最小生成树的总权值

图示

实现代码¶

暴力做法

迭代 $n$ 次：每次从 $T$ 中选一个点加入 $S$，所以总共要执行 $n$ 次。
找最近点 $u$：在 $T$ 中找到 $dis$ 最小的点，加入 $S$，并设 $vis_u = 1$。
更新其他点：对所有未加入的点 $v$，更新：

\[ dis_v = \min(dis_v, a_{u,v}) \]

累计边权和：使用变量 $res$ 累加每次加入的边的权值。
时间复杂度： $O(n^2)$，适合稠密图。

void prim()
{
    // 初始化距离数组
    for (int i = 1; i <= n; i++) dis[i] = 1e9;
    dis[1] = 0; // 从结点 1 开始
    int ans = 0, num = 0;
    for (int i = 1; i <= n; i++) 
    {
        int u = -1;
        for (int v = 1; v <= n; v++) 
        {
            // 求出不在 S 集合且距离最小的点的编号记为 u
            if (!vis[v]) 
            {
                if ((u == -1 || dis[v] < dis[u]))
                {
                    u = v;
                }
            }
        }
        if (dis[u] != 1e9) // 说明 1 到 u 连通
        {
            vis[u] = 1; // 加入 S 集合
            ans += dis[u];
            num++;
            for (int v = 1; v <= n; v++) // 更新其余点的到 S 集合的距离
            {
                dis[v] = min(dis[v], w[u][v]);
            }
        }
    }
    return (num == n ? ans : -1);
}

邻接矩阵存图：注意空间消耗是 $O(n^2)$，适合稠密图。
重边处理：若存在重边，需更新最小权值：

\[ w[u][v] = w[v][u] = \min(w[u][v], val) \]

图可能不连通：若某次选出 $dis_u = 1e9$，说明该图不连通，不存在最小生成树。

堆优化

使用 小根堆 维护 $T$ 集合中与 $S$ 距离最小的点
每次从堆顶取出最小 $dis$ 的点 $u$，加入 $S$。
遍历 $u$ 的邻接边，更新每个点的 $dis$ 并压入堆中。
若最后加入点数 $\ne n$，则图不连通。
时间复杂度： $O(m \log n)$，适合稀疏图。

int prim()
{
    priority_queue<pii, vector<pii>, greater<pii>> q;
    for (int i = 1; i <= n; i++) dis[i] = 1e9;
    dis[1] = 0; 
    q.push({0, 1});
    int ans = 0, num = 0;
    while (!q.empty()) 
    {
        auto now = q.top(); 
        q.pop();
        int d = now.first, u = now.second;
        if (vis[u]) continue;
        vis[u] = 1;
        ans += d; 
        num++;
        for (auto it : e[u]) 
        {
            int v = it.first, w = it.second;
            if (dis[v] > w) 
            {
                dis[v] = w;
                q.push({dis[v], v});
            }
        }
    }
    return (num == n ? ans : -1);
}

总结¶

Prim 算法可以处理负边，因为只关心连接 $S$ 集合的最短边，不涉及路径叠加。
暴力版本（邻接矩阵）：$O(n^2)$
堆优化版本（邻接表）：$O(m \log n)$

Kruskal 算法¶

Kruskal 算法是一种常见并且好写的最小生成树算法，由 Kruskal 发明。该算法的基本思想是从小到大加入边，是个贪心算法。

基本思想¶

它采用的是一种 贪心策略 从小到大选择边，只要不会形成环，就将该边加入生成树。

算法本质¶

把图的边从小到大排序，按顺序尝试加入最小生成树。若两个端点属于不同的连通块，则连接它们。

使用并查集维护连通性，主要适用于稀疏图。

算法流程¶

边排序：将所有边按权重升序排序；
- 因此需要采用直接存边法。
并查集初始化：每个点自成一个集合。
遍历边集：
- 若当前边连接的两个点在不同集合中 $\to$ 加入该边，合并集合；
- 否则跳过（加入会形成环）；
重复上述过程，直到加入 $n - 1$ 条边为止。

无解：若最终选中的边数 $< n-1$，则说明图不连通，最小生成树不存在。

实现代码¶

时间复杂度：$O(m\log{m})$，并查集的操作忽略不计。

vector<array<int, 3>> e;
int find(int x)
{
    if (p[x] != x) return p[x] = find(p[x]);
    return x;
}
void merge(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y) return ;
    p[x] = y;
}
int kruskal()
{
    sort(e.begin(), e.end()); // 按照边权从小到大排序
    for (int i = 1; i <= n; i++) p[i] = i; // 初始化并查集
    int num = 0, ans = 0;
    for (auto it : e)
    {
        int w = it[0], u = it[1], v = it[2];
        if (find(u) != find(v))
        {
            merge(u, v);
            ans += w, num++;
        }
    }
    return (num == n - 1 ? ans : -1);
}
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        // 把边权放第一位，方便排序
        e.push_back({w, u, v});
    }
    cout << kruskal();
}

Kruskal 算法的正确性（反证法）¶

思路：假设当前选中的边 $e$ 未出现在最小生成树 $T$ 中，使用反证法说明其矛盾性。

假设：Kruskal 当前处理边 $e = (u,v)$ 不属于某一棵最小生成树 $T$。

分析：

Kruskal 按边权递增枚举，$e$ 是当前未形成环的最小边。
若将 $e$ 加入 $T$，必然构成一个环。
在环上必有一条边 $e'$ 的权重 $\geq w(e)$。
若 $w(e') > w(e)$，用 $e$ 替换 $e'$ 构造一棵权值更小的生成树 $\Rightarrow$ 与 $T$ 是最小生成树矛盾。

结论：$e$ 必属于某棵最小生成树 $\Rightarrow$ Kruskal 合理有效。

瓶颈生成树¶

定义¶

无向图 $G$ 的瓶颈生成树是这样的一个生成树，它的最大的边权值在 $G$ 的所有生成树中最小。

性质¶

最小生成树是瓶颈生成树的充分不必要条件。

即最小生成树一定是瓶颈生成树，而瓶颈生成树不一定是最小生成树。

关于最小生成树一定是瓶颈生成树这一命题，可以运用反证法证明：

我们设最小生成树中的最大边权为 $w$，如果最小生成树不是瓶颈生成树的话，则瓶颈生成树的所有边权都小于 $w$
我们只需删去原最小生成树中的最长边，用瓶颈生成树中的一条边来连接删去边后形成的两棵树/
树一定比原最小生成树的权值和还要小，这样就产生了矛盾。

次小生成树¶

非严格次小生成树¶

定义¶

在无向图中，边权和最小的满足边权和 大于等于 最小生成树边权和的生成树。

求解方法¶

求出无向图的最小生成树 $T$，设其权值和为 $M$。
遍历每条 未被选中 的边 $e = (u,v,w)$，找到 $T$ 中 $u$ 到 $v$ 路径上边权最大的一条边 $e' = (s,t,w')$，则在 $T$ 中以 $e$ 替换 $e'$，可得一棵权值和为 $M' = M + w - w'$ 的生成树 $T'$
对所有替换得到的答案 $M'$ 取最小值即可

如何求 $u,v$ 路径上的边权最大值呢？

暴力遍历 $u\to v$ 之间的路径求边权最大值，时间复杂度为 $O(n)$。

优化：使用倍增来维护，预处理出每个节点的 $2^i$ 级祖先及到达其 $2^i$ 级祖先路径上最大的边权，这样在倍增求 LCA 的过程中可以直接求得。

暴力具体实现¶

第一步：求出 MST 的权值和记作 $M$，同时给每条边打上标记。
- 标记哪些边属于 MST，哪些边不属于。
- 由于后续需要求生成树上两点路径的最大值，因此需要把生成树真正建立出来

long long kruskal()
{
    for (int i = 1; i <= n; i++) fa[i] = i;
    sort(adj.begin(), adj.end());
    long long res = 0;
    for (auto &[w, u, v, flag] : adj)
    {
        if (find(u) != find(v))
        {
            merge(u, v);
            res += w;
            flag = 1; // 打标记该条边属于 MST 
            // 建立出最小生成树
            e[u].push_back({v, w});
            e[v].push_back({u, w});
        }
    }
    return res;
}

第二步：枚举所有的边 [u, v, w, flag]。
- 若满足 flag == 0，则这条边不属于 MST。
- 需要求出 $u\to v$ 的最大边权记作 mx，然后用这条边替换掉生成树上的最大边。

for (auto [w, u, v, flag] : adj) 
{
    if (flag) continue;
    dfs(u, 0, v, mx);
    mn = min(mn, M + w - mx);
}
cout << mn;

第三步：实现 dfs(int u, int fa, int end, long long &mx) 的函数。
- 其作用为求出 $u\to v$ 的最大边权。

bool dfs(int u, int fa, int end, long long &mx)
{
    if (u == end) return 1;
    for (auto [v, w] : e[u])
    {
        if (v == fa) continue;
        if (dfs(v, u, end, mx) == 1) // u->v 是能走到终点 end
        {
            if (w > mx)
                mx = w;
            return 1;
        }
    }
    return 0;
}

严格次小生成树¶

定义¶

在无向图中，边权和最小的满足边权和 严格大于 最小生成树边权和的生成树。

求解方法¶

考虑刚才的非严格次小生成树求解过程，为什么求得的解是非严格的？

因为最小生成树保证生成树中 $u$ 到 $v$ 路径上的边权最大值一定 不大于 其他从 $u$ 到 $v$ 路径的边权最大值。换言之，当我们用于替换的边的权值与原生成树中被替换边的权值相等时，得到的次小生成树是非严格的。

解决的办法很自然：

维护 $u\to v$ 的最大边权和严格次大边权。
- 保证最大和次大不相等。
在替换时，如果当前边权 $w$ 和最大边权相等。则选择次大。反之选择最大。

这里给出 $O(n)$ 暴力求解树上两点 $u,v$ 路径上最大边权和次大边权的实现，等学习倍增以后转化为倍增处理即可。

long long kruskal()
{
    for (int i = 1; i <= n; i++) fa[i] = i;
    sort(adj.begin(), adj.end());
    long long res = 0;
    for (auto &[w, u, v, flag] : adj)
    {
        if (find(u) != find(v))
        {
            merge(u, v);
            res += w;
            flag = 1; // 这是树边
            // 建立出最小生成树
            e[u].push_back({v, w});
            e[v].push_back({u, w});
        }
    }
    return res;
}
bool dfs(int u, int fa, int end, long long &mx1, long long &mx2)
{
    if (u == end) return 1;
    for (auto [v, w] : e[u])
    {
        if (v == fa) continue;
        if (dfs(v, u, end, mx1, mx2) == 1) // u->v 是能走到终点 end
        {
            if (w > mx1) 
            {
                mx2 = mx1;// 次大变最大
                mx1 = w;
            }
            else if (w != mx1 && w > mx2)
            {
                mx2 = w;
            }
            return 1;
        }
    }
    return 0;
}
int main()
{
    long long M = kruskal();
    long long mn = 1e18, mx1 = 0, mx2 = -1e9;
    for (auto [w, u, v, flag] : adj) 
    {
        if (flag) continue;
        dfs(u, 0, v, mx1, mx2);
        if (mx1 == w) mn = min(mn, M + w - mx2);
        else mn = min(mn, M + w - mx1);
    }
    cout << mn;
    return 0;
}

例题¶

构造完全图¶

题意： 给定一棵树 $T$，包含 $n$ 个节点和 $n-1$ 条边。请你为这棵树补全边，使其变为一个 完全图 $G$，并满足：

图 $G$ 的唯一一棵最小生成树是原始树 $T$
图中所有边有边权（正整数），目标是使总边权和最小
$1 \leq n \leq 10^5$，$1 \leq w \leq 10^5$
完全图：任意两点之间都存在一条边

思路： 要让最小生成树唯一，不能存在权值相等的可替换边

图中若存在多条边同权，可能导致不同合并顺序 $\Rightarrow$多个 MST

Kruskal 决策过程回顾

Kruskal 按边权从小到大排序处理每条边
每次选中边 $[u, v, w]$，若 $u, v$ 不连通 $\Rightarrow$ 合并并加入生成树
若存在另一条边 $[x, y, w]$，且 $x,u$ 属于同一集合，$y,v$ 属于同一集合，也可能被选 $\Rightarrow$ 导致 MST 不唯一

因此避免任何非树边与树边权值相等 $\Rightarrow$ 所有非树边必须 $> w$。

更准确地说：当前连通两个集合最小的边为 $w$，其余可以连通两个集合的边权值至少为 $w+1$。

避免替换：如何控制非树边的权值？

对于树中一条边 $[u, v, w]$，在 Kruskal 中连接了两个集合 $U$ 和 $V$。

若非树边连接了 $U$ 中某点 $x$ 与 $V$ 中某点 $y$，且权值 $\leq w$，则可能替换掉原边。

为防止替换

原树边 $[u,v]$ 保持权值为 $w$
对于所有 $x \in U$, $y \in V$ 且 $(x,y) \ne (u,v)$，添加边权 $\geq w + 1$

数量：对每条树边，其对应跨集合的点对数为 $|U| \times |V| - 1$

实现步骤

对树进行 Kruskal，维护每个集合的大小记为 $sz$。
枚举每条边，设两侧集合大小分别为 $sz_u, sz_v$
原树边设为权值 $w$，其余 $sz_u \times sz_v - 1$ 条补边设为 $w + 1$

总边权 = 树边之和 $+$ 所有补边权和（尽量小）

long long kruskal()
{
    sort(adj.begin(), adj.end(), cmp); // 按照边权从小到大排序
    for (int i = 1; i <= n; i++) p[i] = i, sz[i] = 1;
    long long ans = sum; // sum 为初始树的边权之和
    for (auto it : adj)
    {
        int u = it.u, v = it.v, w = it.w;
        if (find(u) != find(v)) // 对树做 kruskal 这个也可以不写，除非树有环，显然不可能。
        {
            ans += 1ll * (w + 1) * (sz[find(u)] * sz[find(v)] - 1);
            merge(u, v);
        }
    }
    return ans;
}

[ABC383E] Sum of Max Matching¶

题意：

给定一个有 $N$ 个顶点、$M$ 条边的带权无向连通简单图，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边 $(1 \leq i \leq M)$ 连接顶点 $u_i$ 和顶点 $v_i$，权值为 $w_i$，且为双向边。

对于一条路径，其权值定义为该路径上所有边的权值的最大值。记 $f(x, y)$ 为从顶点 $x$ 到顶点 $y$ 的所有路径中权值的最小值。

给定长度为 $K$ 的数列 $(A_1, A_2, \ldots, A_K)$ 和 $(B_1, B_2, \ldots, B_K)$，其中保证 $A_i \neq B_j$ 对任意 $1 \leq i, j \leq K$ 都成立。

你可以任意重排数列 $B$，请最小化 $\displaystyle\sum_{i=1}^{K}f(A_i, B_i)$。

$2 \leq N,M\leq 2 \times 10^5$

新的开始¶

题意： 给定 $n$ 个矿井，为保证电力供应：

至少选择一个矿井建立发电站，费用为 $v_i$。
将当前矿井 $i$ 和已有电力供应的矿井 $j$ 连接，费用为 $p_{i,j}$。

输出所有矿井电力供应的最小花费。

建模思路：点权转边权

原问题中既包含点权（建电站）又包含边权（连线费用），我们希望统一为 纯边权 问题，方便使用最小生成树算法。

转化策略：

引入一个虚拟节点 $n+1$（代表电网中心）
对每个矿井 $i$，连边 $(i, n+1)$，边权为 $v_i$
原有 $p_{i,j}$ 的边保持不变

此时问题转化为在 $n+1$ 个节点构成的图中，构造一棵最小生成树，使得所有节点连通，最小化总成本。

[ABC270F] Transportation¶

题意： 给定 $n$ 个城市，有如下建设方案：

在城市 $i$ 建机场，代价为 $x_i$
在城市 $i$ 建港口，代价为 $y_i$
在 $a_i$ 和 $b_i$ 之间建道路，代价为 $z_i$（共 $m$ 条）

若两个城市满足以下任一条件则可互达：

均有机场或均有港口或直接通过道路相连。

求使所有城市连通的最小代价。$2 \le n, m \le 2 \times 10^5$

思路：

建立两个 虚拟点：

$n+1$：机场中心，与每个城市连接，代价为 $x_i$
$n+2$：港口中心，与每个城市连接，代价为 $y_i$

直接连通关系建边：$a_i \leftrightarrow b_i$，代价 $z_i$

问题转化为：选择若干机场/港口/道路，使得整个图联通，最小化代价。

注意不能直接对 $n+2$ 个点的图求 MST

加入机场虚拟点 $\Rightarrow$ 有可能强制至少选择一个机场
同理，加入港口虚拟点 $\Rightarrow$ 有可能强制选港口
实际上，可能\textbf{只选机场}或\textbf{只选港口}就能使得代价最小。

因此需要分类讨论四种情况：

不建机场、不建港口。只用道路连通。
仅建机场，搭配道路连通。
仅建港口，搭配道路连通。
建机场、建港口，搭配道路连通。

每种情况都跑一遍 Kruskal，取最优答案。

实现细节提示

封装 Kruskal 函数：参数可灵活控制是否加入机场/港口边

long long kruskal(vector<array<int, 3>> &adj, int n)
{
    for (int i = 1; i <= n; i++) fa[i] = i;
    sort(adj.begin(), adj.end());
    ll res = 0, num = 0;
    for (auto [w, u, v] : adj)
    {
        u = find(u), v = find(v);
        if (u != v)
        {
            fa[u] = v;
            res += w;
            num++;
        }
    }
    if (num != n - 1) return 1e18; // 无法连通返回极大值
    return res;
}

// 初始化既不用机场也不用港口
long long ans = kruskal(adj, n);

// 建立机场
vector<array<int, 3>> e = adj;
for (int i = 1; i <= n; i++) e.push_back({x[i], i, n + 1});
ans = min(ans, kruskal(e, n + 1));

// 建立港口
e = adj;
for (int i = 1; i <= n; i++)  e.push_back({y[i], i, n + 1});
ans = min(ans, kruskal(e, n + 1));

// 建立机场和港口
e = adj;
for (int i = 1; i <= n; i++) 
    e.push_back({x[i], i, n + 1}), e.push_back({y[i], i, n + 2});
ans = min(ans, kruskal(e, n + 2));
cout << ans;

[COCI2009-2010#7] SVEMIR¶

题意： 太空帝国希望用隧道连接它的 $N$ 个星球，每个星球有三维坐标 $(x_i, y_i, z_i)$。

在两个星球 $A, B$ 间建隧道的代价是：

现在要求选出 $N-1$ 条隧道，使所有星球联通，且总代价最小。

数据范围：$1 \le N \le 10^5$，$-10^9 \le x_i, y_i, z_i \le 10^9$

优化建图

枚举所有两点建边，时间复杂度 $O(n^2)$，无法接受。
观察代价函数 $\min(|x_i - x_j|, |y_i - y_j|, |z_i - z_j|)$，考虑按每个维度的相邻点建边。
精髓
- 按 $x$ 排序，相邻点建边
- 按 $y$ 排序，相邻点建边
- 按 $z$ 排序，相邻点建边
最多生成 $3(n - 1)$ 条边，然后跑 Kruskal 求 MST。

正确性证明

生成的边能构成生成树

在任意一维（如 $x$）排序后，相邻点间连边就已构成一棵生成树；三维共同构成更稠密的图，必能连通。

能得到最小生成树

反证法：若最小生成树 $T'$ 中包含一条不在我们建的边集内的边 $(a, b)$。

那么意味着 $(a, b)$ 在每个维度排序中都不相邻。

那么在与该维度相近的点之间（例如 $a < c < b$），有边 $(a, c), (c, b)$ 代价 $\le (a, b)$。
可将 $(a, b)$ 替换成 $(a, c), (c, b)$ 构成新树，总权值不增，构成环。
删除环中任意较大代价边，可得更优方案，矛盾。

[ABC364F] Range Connect MST¶

题意：

有一个包含 $N+Q$ 个顶点的图，顶点编号为 $1, 2, \ldots, N+Q$。初始时图中没有任何边。

对于该图，依次进行 $i=1,2,\ldots,Q$ 的如下操作：

对于每个满足 $L_i \leq j \leq R_i$ 的整数 $j$，在顶点 $N+i$ 与顶点 $j$ 之间添加一条无向边，边的代价为 $C_i$。

所有操作结束后，请判断该图是否连通。如果连通，请求出该图的最小生成树的总代价。

其中，最小生成树指的是所有顶点连通且边权和最小的生成树。

$1 \leq N, Q \leq 2 \times 10^5$

思路：

回顾 Kruskal 的过程不难想到首先把询问全部存储下来以后，按照代价 $C_i$ 从小到大依次处理。

[ABC355F] MST Query¶

题意：

给定一个有 $N$ 个顶点、$N-1$ 条边的带权无向连通图 $G$，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $N-1$。第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$，权值为 $c_i$。

有 $Q$ 个查询，请依次处理。第 $i$ 个查询如下：

给定整数 $u_i, v_i, w_i$，向 $G$ 中添加一条连接顶点 $u_i$ 和顶点 $v_i$、权值为 $w_i$ 的边。之后，输出 $G$ 的最小生成树中所有边权的和。

数据范围：$2 \leq N \leq 2 \times 10^5$，$1 \leq Q \leq 2 \times 10^5$，$1 \leq c_i, w_i \leq 10$

[USACO15FEB] Superbull S¶

题意： Superbull 是一场淘汰赛，有 $N$ 支队伍（$1 \leq N \leq 2000$），每支队伍有一个唯一的团队 ID（范围在 $[1, 2^{30}-1]$）。

每场比赛的得分为两支队伍 ID 的按位异或（XOR）值，例如 $12 \oplus 20 = 24$。

你可以自由安排比赛顺序，每场淘汰一支队伍，直到剩下最后一支。你的目标是设计一种比赛方案，使得所有比赛的总得分最大。

[SCOI2012] 滑雪¶

题意： 给定 $n$ 个景点和 $m$ 条滑雪道，每个景点有一个高度 $h_i$。若 $h_u \ge h_v$，则可以从 $u$ 滑到 $v$。你可以使用“时间胶囊”返回经过的任意景点（不计滑行距离）。

现在从 $1$ 号景点出发，求：

经过最多的景点数（不能重复计数）
在满足点数最多的前提下，总滑行距离最小

数据范围：$1 \leq n \leq 10^5$, $1 \leq m \leq 10^6$, $h_i \leq 10^9$