参考《算法竞赛进阶指南》、AcWing题库

最小生成树

给定一张边带权的无向图 $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 算法总是维护无向图的最小生成森林。最初, 可认为生成森林由零条边构成, 每个节点各自构成一棵仅包含一个点的树。

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

详细来说, Kruskal 算法的流程如下:

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

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

// Kruskal算法，O(mlogm)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

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\left(n^{2}\right)$ , 可以用二叉堆优化到 $O(m \log n)$ 。但用二叉堆优化不如直接使用 Kruskal 算法更加方便。因此, Prim 主要用于稠密图, 尤其是完全图的最小生成树的求解。

// Prim算法，O(n^2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[3010][3010], d[3010];
bool v[3010];
int n, m, ans;

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]);
	}
}

int main() {
	cin >> n >> m;
	// 构建邻接矩阵
	memset(a, 0x3f, sizeof(a));
	for (int i = 1; i <= n; i++) a[i][i] = 0;
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		a[y][x] = a[x][y] = min(a[x][y], z);
	}
	// 求最小生成树
	prim();
    for (int i = 2; i <= n; i++) ans += d[i];
    cout << ans << endl;
}

例题

346. 走廊泼水节

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

求增加的边的权值总和最小是多少。

注意： 树中的所有边权均为整数，且新加的所有边权也必须为整数。

输入格式

第一行包含整数 $t$ ，表示共有 $t$ 组测试数据。

对于每组测试数据，第一行包含整数 $N$ 。

接下来 $N-1$ 行，每行三个整数 $X,Y,Z$ ，表示 $X$ 节点与 $Y$ 节点之间存在一条边，长度为 $Z$ 。

输出格式

每组数据输出一个整数，表示权值总和最小值。

每个结果占一行。

数据范围

$1 \le N \le 6000$
$1 \le Z \le 100$

输入样例：

输出样例：

1
2

4
17

算法分析

Solution

347. 野餐规划

一群小丑演员，以其出色的柔术表演，可以无限量的钻进同一辆汽车中，而闻名世界。

现在他们想要去公园玩耍，但是他们的经费非常紧缺。

他们将乘车前往公园，为了减少花费，他们决定选择一种合理的乘车方式，可以使得他们去往公园需要的所有汽车行驶的总公里数最少。

为此，他们愿意通过很多人挤在同一辆车的方式，来减少汽车行驶的总花销。

由此，他们可以很多人驾车到某一个兄弟的家里，然后所有人都钻进一辆车里，再继续前进。

公园的停车场能停放的车的数量有限，而且因为公园有入场费，所以一旦一辆车子进入到公园内，就必须停在那里，不能再去接其他人。

现在请你想出一种方法，可以使得他们全都到达公园的情况下，所有汽车行驶的总路程最少。

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

输入格式

第一行包含整数 $n$ ，表示人和人之间或人和公园之间的道路的总数量。

接下来 $n$ 行，每行包含两个字符串 $A、B$ 和一个整数 $L$ ，用以描述人 $A$ 和人 $B$ 之前存在道路，路长为 $L$ ，或者描述某人和公园之间存在道路，路长为 $L$ 。

道路都是双向的，并且人数不超过 $20$ ，表示人的名字的字符串长度不超过 $10$ ，公园用 Park 表示。

再接下来一行，包含整数 $s$ ，表示公园的最大停车数量。

你可以假设每个人的家都有一条通往公园的道路。

输出格式

输出 Total miles driven: xxx，其中 $xxx$ 表示所有汽车行驶的总路程。

输入样例：

10
Alphonzo Bernardo 32
Alphonzo Park 57
Alphonzo Eduardo 43
Bernardo Park 19
Bernardo Clemenzi 82
Clemenzi Park 65
Clemenzi Herb 90
Clemenzi Eduardo 109
Park Herb 24
Herb Eduardo 79
3

输出样例：

1	Total miles driven: 183

算法分析

Solution

348. 沙漠之王

大卫大帝刚刚建立了一个沙漠帝国，为了赢得他的人民的尊重，他决定在全国各地建立渠道，为每个村庄提供水源。

与首都相连的村庄将得到水资源的浇灌。

他希望构建的渠道可以实现单位长度的平均成本降至最低。

换句话说，渠道的总成本和总长度的比值能够达到最小。

他只希望建立必要的渠道，为所有的村庄提供水资源，这意味着每个村庄都有且仅有一条路径连接至首都。

他的工程师对所有村庄的地理位置和高度都做了调查，发现所有渠道必须直接在两个村庄之间水平建造。

由于任意两个村庄的高度均不同，所以每个渠道都需要安装一个垂直的升降机，从而使得水能够上升或下降。

建设渠道的成本只跟升降机的高度有关，换句话说只和渠道连接的两个村庄的高度差有关。

需注意，所有村庄（包括首都）的高度都不同，不同渠道之间不能共享升降机。

输入格式

输入包含多组测试数据。

每组测试数据第一行包含整数 $N$ ，表示村庄（包括首都）的总数目。

接下来 $N$ 行，每行包含三个整数 $x，y，z$ ，描述一个村庄的地理位置， $(x,y)$ 为该村庄的位置坐标， $z$ 为该村庄的地理高度。

第一个被描述的村庄即为首都。

当输入一行为 $0$ 时，表示输入终止。

输出格式

每组数据输出一个结果，每个结果占一行。

结果为一个保留三位小数的实数，表示渠道的总成本和总长度的比值的最小值。

数据范围

$2 \le N \le 1000$ ,
$0 \le x,y < 10000$ ,
$0 \le z \le 10000000$

输入样例：

输出样例：

1.000

算法分析

Solution

349. 黑暗城堡

在顺利攻破 Lord lsp 的防线之后，lqr 一行人来到了 Lord lsp 的城堡下方。

Lord lsp 黑化之后虽然拥有了强大的超能力，能够用意念力制造建筑物，但是智商水平却没怎么增加。

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

lqr 深知 Lord lsp 的想法，为了避免每次都要琢磨两个房间之间的最短路径，Lord lsp 一定会把城堡修建成树形的。

但是，为了尽量提高自己的移动效率，Lord lsp 一定会使得城堡满足下面的条件：

设 $D[i]$ 为如果所有的通道都被修建，第 $i$ 号房间与第 $1$ 号房间的最短路径长度；而 $S[i]$ 为实际修建的树形城堡中第 $i$ 号房间与第 $1$ 号房间的路径长度；要求对于所有整数 $i$ ，有 $S[i]=D[i]$ 成立。

为了打败 Lord lsp，lqr 想知道有多少种不同的城堡修建方案。

你需要输出答案对 $2^{31}–1$ 取模之后的结果。

输入格式

第一行有两个整数 $N$ 和 $M$ 。

之后 $M$ 行，每行三个整数 $X，Y$ 和 $L$ ，表示可以修建 $X$ 和 $Y$ 之间的一条长度为 $L$ 的通道。

输出格式

一个整数，表示答案对 $2^{31}–1$ 取模之后的结果。

数据范围

$2 \le N \le 1000$ ,
$N-1 \le M \le N(N-1)/2$ ,
$1 \le L \le 100$

输入样例：

输出样例：