第十一章 最小生成树
树是一种特殊的图，具有很多特殊的性质。生成树问题研究的是将图中的所有顶点保留，但只选择图中的部分边，得到一颗树（也就是图的生成树）的问题。最小生成树则是在这些生成树中，边权之和最小的生成树。
最小生成树及其应用
例题1：P3366 【模板】最小生成树
解法 $1$（$\text{Prim} 算法）：
- 将 $1$ 号点加入当前生成树中并打上标记，同时更新 $dis$ 数组；
- 选择所有未标记的点中 $dis$ 最小的点；
- 将该点加入当前生成树并打上标记；
- 使用与该点相连的所有连边更新 $dis$ 数组；
- 重复第 $2$ 到 $4$ 步，直到所有点都已经被标记或者所有未标记的点都不存在连边与已标记的点直接连接。
需要注意的是，如果出现所有未标记的点都不存在连边与已标记的点直接相连的情况就意味着图不连通。此时也应当结束程序。可以再记录一个变量 $tot$，代表打上标记的点的数量。如果最后 $tot \neq n$，则可以直接判定无解。
void Prim() {
for (int i = 1; i <= n; i++) vertex[i].dis = inf;
vertex[0].dis = inf;
vertex[1].dis = 0;
while (true) {
int u = 0;
for (int i = 1; i <= n; i++) {
if (!vertex[i].vis && vertex[i].dis < vertex[u].dis) {
u = i;
}
}
if (!u) break;
tot++;
vertex[u].vis = true;
for (int e = vertex[u].head; e; e = edge[e].next) {
int v = edge[e].head;
int w = edge[e].weight;
if (vertex[v].dis > w) {
vertex[v].dis = w;
}
}
}
}
这段程序的时间复杂度为 $\mathcal O(n^2 + m)$。但如果 $n$ 较大则可能出现超时的情况。
容易发现，这一算法与 $Dijkstra$ 算法十分相似。于是可以采用一个类似于 $Dijkstra$ 算法的堆来进行优化，每次更新 $dis$ 数组后将 $dis$ 值与对应点存入一个优先队列，依据 $dis$ 值排序。这样就可以将时间复杂度优化到 $\mathcal O(m \log m)$。
void Prim() {
for (int i = 1; i <= n; i++) vertex[i].dis = inf;
vertex[1].dis = 0;
std::priority_queue<Vertex> q;
q.push(vertex[1]);
while (!q.empty()) {
int u = q.top().vertex;
if (vertex[u].vis) continue;
tot++;
vertex[u].vis = true;
for (int e = vertex[u].head; e; e = edge[e].next) {
int v = edge[e].head;
int w = edge[e].weight;
if (vertex[v].dis > w) {
vertex[v].dis = w;
q.push(vertex[v]);
}
}
}
return;
}
解法 $2$（$\text{Kruscal}$ 算法）：
- 将所有的边从小到大排序；
- 将所有点分别放入各自的并查集中；
- 选择所有未使用的边中边权最小的；
- 若该边所连接的两个点已经连通，则舍去，否则合并这两个并查集；
- 重复第 $3$ 到 $4$ 步，直到所有点都已经被标记或所有未标记的点都不存在连边与已标记的点直接连接。
因为 $\text{Kruscal}$ 算法的瓶颈在于将所有的边排序，所以复杂度为 $\mathcal O(m \log m)$。
void Kruscal() {
std::sort(edge + 1, edge + ecnt + 1);
for (int e = 1; e <= ecnt; e++) {
int u = DSU.Find(edge[e].tail);
int v = DSU.Find(edge[e].head);
if (u == v) continue;
DSU.Union(u, v);
cnt++;
}
}
在稠密图中，原版的 $\text{Prim}$ 算法复杂度较优，但在稀疏图中，堆优化的 $\text{Prim}$ 以及 $\text{Kruscal}$ 算法表现会更好。
例题2：P1194 买礼物
由于涉及两点之间的关系，考虑建图。根据各点间的优惠关系来建图，边权就代表优惠后的价格。而对于原价购买，可以建立一个超级源点（设为 $0$ 号点）。从 $0$ 号点向每条边连一个边权为 $A$ 的边，代表原价购买这条边的价格。
例题3：CF472D Design Tutorial: Inverse the Problem
按照两两点对之间的距离见图。显然，如果这 $n$ 个点可以构成一颗树，那么这棵树一定是该图的生成树。进一步讨论这棵树的性质。对于像个距离较大的点，它们的路径上很有可能会经过其他点，但对于相隔较小的点，路径上经过其他点就会比较困难。不难理解，这棵树应该是由若干相隔较小的点直接相连构成的，所以其边权和应该很小。这时可以猜测，这棵树可能就是原图点最小生成树。
回顾 $\text{Kruscal}$ 的过程。一条 $u$ 到 $v$ 的边权为 $w$ 的边属于最小生成树，当且仅当所有边权小于 $w$ 的边组成的图没能使 $u, v$ 两个点连通。这也就意味着在最后的生成树上这两个点的路径一定会经过至少一条边权大于等于 $w$ 的边，这样两点之间的距离一定就大于等于 $w$，当且仅当 $u$ 与 $v$ 直接相连才能取等。因此只有在这棵树是最小生成树的时候，它才可能是满足条件的树。
由于是稠密图，在求生成树时，使用原版 $\text{Prim}$ 算法复杂度更优。在维护 $dis$ 的时候，再维护一个数组，表示 $dis$ 值表示的边从哪里来，与 $dis$ 值一同更新。在每个点打上标记之前进行连边，这样在算法结束的时候最小生成树也就建好了。接着只需要从每个点开始 $\text{DFS}$ 遍历验证，查看各点间距离是否与输入数据一致即可。
次小生成树
例4：P4180 [BJWC2010] 严格次小生成树
由于严格次小生成树的边权和仅大于最小生成树边权和，因此可以猜测，严格次小生成树很可能就是在最小生成树上替换一条或几条边得到。事实上，可以证明，一定存在一棵严格次小生成树，使得它与某颗最小生成树仅有一条边的差距。
可以考虑在建完最小生成树之后寻找那条不属于最小生成树，但属于严格次小生成树的边。枚举枚举每一条非树边，在加入这条边之后，生成树上出现了一个环。再断掉环中其他边里面边权最大的边（若该边权与环内其他边中边权最大者相等，则断掉边权次大者。注意可能不存在边权次大的边），那么就得到了包含这条边的最小生成树中权值最小者。将所有上述生成树权值和取 $\text{min}$ 后，就可以得到最终的答案。
采取树上倍增的方法，定义 $1$ 为树根，并存储每个点向上 $2^i$ 条边的最大值与次大值。在寻找时，通过倍增取出这些最大值与次大值并依次更新，就可以得到需要断的边的权值。注意在存储和寻找次大值时的分类讨论。
由于是稀疏图，最小生成树采用 $\mathcal O(n \log n)$ 的 $\text{Kruscal}$ 算法或是堆优化 $\text{Prim}$ 算法。
void DFS(int u) {
vertex[u].dep = vertex[ST.f[u][0]].dep + 1;
for (int p = 1; p <= logN; p++) {
ST.f[u][p] = ST.f[ST.f[u][p - 1]][p - 1];
if (ST.fir[u][p - 1] == ST.fir[ST.f[u][p - 1]][p - 1]) {
ST.fir[u][p] = ST.fir[u][p - 1];
ST.sec[u][p] = std::max(ST.sec[u][p - 1], ST.sec[ST.f[u][p - 1]][p - 1]);
}
if (ST.fir[u][p - 1] > ST.fir[ST.f[u][p - 1]][p - 1]) {
ST.fir[u][p] = ST.fir[u][p - 1];
ST.sec[u][p] = std::max(ST.sec[u][p - 1], ST.fir[ST.f[u][p - 1]][p - 1]);
}
if (ST.fir[u][p - 1] < ST.fir[ST.f[u][p - 1]][p - 1]) {
ST.fir[u][p] = ST.fir[ST.f[u][p - 1]][p - 1];
ST.sec[u][p] = std::max(ST.fir[u][p - 1], ST.sec[ST.f[u][p - 1]][p - 1]);
}
}
for (int e = vertex[u].head; e; e = edge[e].next) {
int v = edge[e].head;
int w = edge[e].weight;
if (v == ST.f[u][0]) continue;
if (!edge[e].choose) continue;
ST.f[v][0] = u;
ST.fir[v][0] = w;
DFS(v);
}
return;
}
int LCA(int u, int v) {
if (vertex[u].dep < vertex[v].dep) std::swap(u, v);
for (int p = logN; p >= 0; p--) if (vertex[ST.f[u][p]].dep >= vertex[v].dep) u = ST.f[u][p];
if (u == v) return u;
for (int p = logN; p >= 0; p--) if (ST.f[u][p] != ST.f[v][p]) u = ST.f[u][p], v = ST.f[v][p];
return ST.f[u][0];
}
lxl calc(int u, int v, int w) {
int g = LCA(u, v);
lxl fir = 0;
lxl sec = 0;
for (int p = logN; p >= 0; p--) {
if (vertex[ST.f[u][p]].dep >= vertex[g].dep) {
if (fir == ST.fir[u][p]) sec = std::max(sec, ST.sec[u][p]);
if (fir > ST.fir[u][p]) sec = std::max(sec, ST.fir[u][p]);
if (fir < ST.fir[u][p]) sec = std::max(fir, ST.sec[u][p]), fir = ST.fir[u][p];
u = ST.f[u][p];
}
if (vertex[ST.f[v][p]].dep >= vertex[g].dep) {
if (fir == ST.fir[v][p]) sec = std::max(sec, ST.sec[v][p]);
if (fir > ST.fir[v][p]) sec = std::max(sec, ST.fir[v][p]);
if (fir < ST.fir[v][p]) sec = std::max(fir, ST.sec[v][p]), fir = ST.fir[v][p];
v = ST.f[v][p];
}
}
if (w != fir) return sum - fir + w;
if (sec != w) return sum - sec + w;
return lnf;
}
void mian() {
Kruscal();
DFS(1);
ans = lnf;
for (int e = 1; e <= m; e++) {
int u = edge[e].tail;
int v = edge[e].head;
int w = edge[e].weight;
if (edge[e].choose) continue;
ans = std::min(ans, calc(u, v, w));
}
std::cout << ans << '\n';
return;
}