0x62 最小生成树

给定一张边带权的无向图 $G = (V, E)$ ， $n = |V|$ ， $m = |E|$ 。由 $V$ 中全部 $n$ 个顶点和 $E$ 中 $n - 1$ 条边构成的无向连通子图被称为 $G$ 的一棵生成树。边的权值之和最小的生成树被称为无向图 $G$ 的最小生成树（Minimum Spanning Tree, MST）。

定理

任意一棵最小生成树一定包含无向图中权值最小的边。

证明：

反证法。假设无向图 $G = (V, E)$ 存在一棵最小生成树不包含权值最小的边。设 $e = (x, y, z)$ 是无向图中权值最小的边。把 $e$ 添加到树中， $e$ 会和树上从 $x$ 到 $y$ 的路径一起构成一个环，并且环上其他边的权值都比 $z$ 大。因此，用 $e$ 代替环上的其他任意一条边，会形成一棵权值和更小的生成树，与假设矛盾。故假设不成立，原命题成

立。

证毕。

推论

给定一张无向图 $G = (V, E)$ ， $n = |V|$ ， $m = |E|$ 。从 $E$ 中选出 $k < n - 1$ 条边构成 $G$ 的一个生成森林。若再从剩余的 $m - k$ 条边中选 $n - 1 - k$ 条添加到生成森林中，使其成为 $G$ 的生成树，并且选出的边的权值之和最小，则该生成树一定包含这 $m - k$ 条边中连接生成森林的两个不连通节点的权值最小的边。

Kruskal 算法

Kruskal算法就是基于上述推论的。Kruskal算法总是维护无向图的最小生成森林。最初，可认为生成森林由0条边构成，每个节点各自构成一棵仅包含一个点的树。

在任意时刻，Kruskal 算法从剩余的边中选出一条权值最小的，并且这条边的两个端点属于生成森林中两棵不同的树（不连通），把该边加入生成森林。图中节点的连通情况可以用并查集维护。

详细来说，Kruskal算法的流程如下：

建立并查集，每个点各自构成一个集合。
把所有边按照权值从小到大排序，依次扫描每条边 $(x, y, z)$ 。
若 $x, y$ 属于同一集合（连通），则忽略这条边，继续扫描下一条。
否则，合并 $x, y$ 所在的集合，并把 $z$ 累加到答案中。
所有边扫描完成后，第 4 步中处理过的边就构成最小生成树。

时间复杂度为 $O(m \log m)$ 。

struct rec { int x, y, z; } edge[500010];
int fa[100010], n, m, ans;
bool operator <(rec a, rec b) {
    return a.z < b.z;
}
int get(int x) {
    if (x == fa[x]) return x;
    return fa[x] = get(fa[x]);
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].z);
    // 按照边权排序

sort(edge + 1, edge + m + 1); // 并查集初始化  
for (int i = 1; i <= n; i++) fa[i] = i; // 求最小生成树  
for (int i = 1; i <= m; i++) { int x = get(edge[i].x); int y = get(edge[i].y); if (x == y) continue; fa[x] = y; ans += edge[i].z; }  
cout << ans << endl;

Prim算法

Prim 算法同样基于上述推论，但思路略有改变。Prim 算法总是维护最小生成树的一部分。最初，Prim 算法仅确定 1 号节点属于最小生成树。

在任意时刻，设已经确定属于最小生成树的节点集合为 $T$ ，剩余节点集合为 $S$ 。Prim算法找到 $\min_{x\in S,y\in T}\{z\}$ ，即两个端点分别属于集合 $S,T$ 的权值最小的边，然后把点 $x$ 从集合 $S$ 中删除，加入到集合 $T$ ，并把 $z$ 累加到答案中。

具体来说，可以维护数组 $d$ ：若 $x \in S$ ，则 $d[x]$ 表示节点 $x$ 与集合 $T$ 中的节点之间权值最小的边的权值。若 $x \in T$ ，则 $d[x]$ 就等于 $x$ 被加入 $T$ 时选出的最小边的权值。

可以类比Dijkstra算法，用一个数组标记节点是否属于 $T$ 。每次从未标记的节点中选出 $d$ 值最小的，把它标记（新加入 $T$ ），同时扫描所有出边，更新另一个端点的 $d$ 值。最后，最小生成树的权值总和就是 $\sum_{x=2}^{n} d[x]$ 。

Prim 算法的时间复杂度为 $O(n^{2})$ ，可以用二叉堆优化到 $O(m \log n)$ 。但用二叉堆优化不如直接使用 Kruskal 算法更加方便。因此，Prim 主要用于稠密图，尤其是完全图的最小生成树的求解。

int a[3010][3010], d[3010], n, m, ans; bool v[3010];  
void prim() {  
    memset(d, 0x3f, sizeof(d));  
    memset(v, 0, sizeof(v));  
    d[1] = 0;

for (int i = 1; i < n; i++) {
    int x = 0;
    for (int j = 1; j <= n; j++) {
        if (!v[j] && (x == 0 || d[j] < d[x])) x = j;
        v[x] = 1;
    for (int y = 1; y <= n; y++) {
        if (!v[y]) d[y] = min(d[y], a[x][y]);
    }
}

【例题】走廊泼水节 TYVJ1391

给定一棵 $N$ 个节点的树, 要求增加若干条边, 把这棵树扩充为完全图, 并满足图的唯一最小生成树仍然是这棵树。求增加的边的权值总和最小是多少。

数据范围： $N\leq 6000$ ，原有的边权均为非负整数。

$N$ 个节点的树有 $N - 1$ 条边。把这 $N - 1$ 条边按照权值从小到大排序，依次扫描每条边，执行一个类似于Kruskal算法的过程。

设当前扫描到边 $(x, y, z)$ ， $x$ 所在的并查集为 $S_x$ ， $y$ 所在的并查集为 $S_y$ ，此时应该合并 $S_x$ 与 $S_y$ 。合并后的集合 $S_x \cup S_y$ 构成一棵树的结构。

$\forall u \in S_x, v \in S_y$ ，若 $(u, v) \neq (x, y)$ ，则在最终的完全图中，我们肯定需要在 $(u, v)$ 之间增加一条边。于是，无向边 $(u, v)$ 、 $S_x$ 中从 $u$ 到 $x$ 的路径、无向边 $(x, y)$ 以及

$S_{y}$ 中从 $\pmb{v}$ 到 $\mathcal{V}$ 的路径共同构成一个环。如右图所示。

根据本节开头提到的推论，为了保证 $(x,y)$ 一定在最小生成树中，就必须让 $(x,y)$ 是连接集合 $S_{x}$ 与 $S_{y}$ 的权值最小的边（否则就有“用 $(u,v)$ 替换 $(x,y)$ ”的方案）。因此， $(u,v)$ 的边权应该定为 $z + 1$ 。

$S_{x}$ 与 $S_{y}$ 之间一共会增加 $\left|S_{x}\right|*\left|S_{y}\right| - 1$ 条边，

所以我们把 $(z + 1)*\left(|S_x|*|S_y| - 1\right)$ 累加到答案中即可。算法的时间复杂度为 $O(N\log N)$ 。

struct rec { int x, y, z; } edge[6010];
int fa[6010], s[6010], n, T;
long long ans;
bool operator <(rec a, rec b) {
    return a.z < b.z;
}
int get(int x) {
    if (x == fa[x]) return x;
    return fa[x] = get(fa[x]);
}
int main() {
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i < n; i++) {
            scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].z);
            sort(edge + 1, edge + n);
        }
        for (int i = 1; i <= n; i++) {
            fa[i] = i, s[i] = 1;
        }
        ans = 0;
    for (int i = 1; i < n; i++) {
        int x = get(edge[i].x);
        int y = get(edge[i].y);
        if (x == y) continue;
        ans += (long long)(edge[i].z + 1) * (s[x] * s[y] - 1);
        fa[x] = y;
        s[y] += s[x];
    }
};

}cout<<ans<<endl;1

【例题】Picnic Planning POJ1639

给定一张 $N$ 个点 $M$ 条边的无向图，求出无向图的一棵最小生成树，满足1号节点的度数不超过给定的整数 $S$ 。 $N \leq 30$ 。

首先，去掉1号节点之后，无向图可能会分成若干个连通块。可以用深度优先遍历划分出图中的每个连通块。设连通块共有 $T$ 个，若 $T > S$ ，则本题无解。

对于每个连通块，在这个连通块内部求出它的最小生成树，然后从连通块中选出一个节点 $p$ 与1号节点相连，其中无向边 $(1, p)$ 的权值尽量小。

此时，我们已经得到了原无向图的一棵生成树，1号节点的度数为 $T$ 。我们还可以尝试改动 $S - T$ 条边，让答案更优。

考虑无向图中从节点1出发的每条边 $(1,x)$ ，边权为 $z$ 。如果 $(1,x)$ 还不在当前的生成树中，那么继续找到当前生成树中从 $x$ 到1的路径上权值最大的边 $(u,v)$ ，边权为 $w$ 。求出使得 $w - z$ 最大的点 $x_0$ 。若 $x_0$ 对应的 $w_0 - z_0 > 0$ ，则从树中删掉边 $(u_0,v_0)$ ，加入边 $(1,x_0)$ ，答案就会变小 $w_0 - z_0$ 。

重复上一步 $S - T$ 次，或者直到 $w_0 - z_0 \leq 0$ ，就得到了题目所求的最小生成树。

【例题】最优比率生成树 FOJ2728

给定一张 $N$ 个点、 $M$ 条边的无向图 $(1 \leq N, M \leq 10000)$ ，图中每条边 $e$ 都有一个收益 $C_e$ 和一个成本 $R_e$ 。求该图的一棵生成树 $T$ ，使树中各边的收益之和除以成本之和，即 $\sum_{e \in T} C_e / \sum_{e \in T} R_e$ 最大。

这是一道0/1分数规划问题，请读者回顾0x39节的内容。我们可以用二分答案来求解本题。设当前二分的值为mid。

根据0/1分数规划模型，我们只需构建一张新的无向图，图的结构不变，但每条边只有一个权值 $C_e - \text{mid} * R_e$ 。在新的无向图中求最大生成树，若最大生成树上的边权之和非负，则令 $l = \text{mid}$ ，否则令 $r = \text{mid}$ 。

当二分结束时， $(l + r) / 2$ 就是本题的答案。

【例题】黑暗城堡

在顺利攻破 Lordlsp 的防线之后, lqr 一行人来到了 Lordlsp 的城堡下方。Lordlsp 黑化之后虽然拥有了强大的超能力, 能够用意念力制造建筑物, 但是智商水平却没怎么

增加。现在lqr已经搞清楚黑暗城堡有 $N$ 个房间 $(1\leq N\leq 1000)$ ， $M$ 条可以制造的双向通道，以及每条通道的长度。

Iqr 深知 Lord lsp 的想法，为了避免每次都要琢磨两个房间之间的最短路径，Lord lsp 一定会把城堡修建成树形的；但是，为了尽量提高自己的移动效率，Lord lsp 一定会使得城堡满足下面的条件：设 $D[i]$ 为如果所有的通道都被修建，第 $i$ 号房间与第 1 号房间的最短路径长度；而 $S[i]$ 为实际修建的树形城堡中第 $i$ 号房间与第 1 号房间的路径长度；要求对于所有整数 $i (1 \leq i \leq N)$ ，有 $S[i] = D[i]$ 成立。

为了打败 Lord lsp, lqr 想知道有多少种不同的城堡修建方案。于是 lqr 向 applepi 提出了这个问题。因为 applepi 还要忙着出模拟赛, 所以这个任务就交给你了。当然, 你只需要输出答案对 $2^{31} - 1$ 取模之后的结果就行了。

我们可以用Dijkstra算法求出1号房间到每个房间的单源最短路。把树形城堡看作以1为根的有根树。根据题目要求，若 $x$ 是 $y$ 的父节点， $x, y$ 之间的通道长度为 $z$ ，则应该有： $\text{dist}[y] = \text{dist}[x] + z$ 。

事实上，我们把满足题目要求的树结构，即对任意一对父子节点 $x, y$ 都有上式成立的树结构，称为图的一棵最短路径生成树。

我们可以把所有节点按照dist值排序，从小到大依次考虑把每个节点 $p$ 加入树形城堡有多少种方法。与Prim算法类似，我们维护“最短路径生成树”的一部分，记为 $T$ 。统计有多少个节点 $x$ 满足 $x \in T$ 并且 $\text{dist}[p] = \text{dist}[x] + \text{edge}(x, p)$ ，其中edge表示边的长度。让 $p$ 与其中任意一个 $x$ 相连，都符合题目的要求。

根据乘法原理，我们把每一步统计出的数量乘起来，就得到了整道题目的答案。

在有向图中，有一个与无向图最小生成树类似的问题，称为最小树形图问题。这超出了我们的讨论范围，感兴趣的读者可以阅读最小树形图的朱-刘算法及相关资料。

0x62_最小生成树