最小生成树学习笔记

· · 个人记录

基本概念

定义：树是一个连通且无环的简单无向图。

一个 n 树有以下三个特点：

1) 联通。

2) 无环。

3) n-1 条边。

上面任意两个条件满足都可以得出这个图是一个树。

由此我们还可以得到这个结论：

 树中任意两个点有且只有一条简单路径。

生成树指的是在一个无向连通图中包含所有图中节点，并且边都为原图中的边的一棵树。

最小生成树的英文是 Mininum Spanning Tree（MST） ，指的是一张图中边权之和最小的生成树。不过它也可以指我们定义的某种属性最优的生成树（比如边权和最大，极差最大等）。

Kruskal算法

思想

每次选当前剩余的边权最小的边并且这条边现在连接不同区域。简单粗暴

这很明显是一个贪心思想，但它为什么是对呢？

证明

反证法，假设现在已经连了若干条边（还没连完），如果不连当前边权最小且连接两个不同区域的边，叫它 E。我们假设不加 E 所形成的生成树一定是最小生成树。

那么这两个区域最后必然要连起来，所以我们必然还要连若干条其他的边使得他们联通，而他们的和肯定不大于 E（因为 E 是当前边权最小的，而我们至少选一条边权不小于 E 的边），而这样最终连成的生成树依然有 n-1 条边且联通。

最后形成的树中再加上 E 则会形成环，而环中必有晚于 E 加入的边，否则在放弃连 E 的那个时刻不连通的区域，之后也无法连通。

这时我们需要在环中删去一条晚于 E 加入的边，这样生成的图中中依然有 n-1 条边，且依然是联通的，所以这依然是一棵树，而我们去掉的边的边权是不小于 E 的边权，所以这时最小生成树的权值不会更大，但有可能更小，所以不选 E 所最终形成生成树不一定是最小生成树，与假设矛盾。

所以而我们选 E 一定是最优的。

实现

我们发现，动态维合并两个点所在连通块与两个点是否在一个连通块的操作可以用并查集来维护，平均每次 O(1)，所以我们实现步骤如下：

1) 记录每条边两个端点以及边权并按边权从小到大排序。

2) 建立一个 n 个点的并查集，初始时每个点都自己是一个连通块。

3) 循环 m 条边，只要当前边所连接两个端点不在同一连通块就加入这条边，跟新答案并合并连通块。

这样我们就求出了最小生成树。

因为正常排序会用快排，所以时间复杂度是： O(m \log m + m\alpha(n))=O(m \log m +m )=O(m \log m) 。

代码：

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

struct DSU {
    vector<int> p, sz;
    DSU () {}
    DSU (int x) {
        p.assign(x + 1, 0), sz.assign(x + 1, 0);
        for (int i = 1; i <= x; i++)
            p[i] = i, sz[i] = 1;
    }
    int fnd(int x) {
        if (p[x] == x)
            return x;
        return p[x] = fnd(p[x]);
    }
    bool chk(int x, int y) {
        return fnd(x) == fnd(y); 

    }
    void unn(int x, int y) {
        int rx = fnd(x), ry = fnd(y);
        if (rx == ry)
            return;
        if (sz[rx] < sz[ry])
            swap(rx, ry);
        sz[rx] += sz[ry], p[ry] = rx;
    }
} d;
struct Edge {
    int u, v, w;
    Edge (int _u = 0, int _v = 0, int _w = 0) :
        u(_u), v(_v), w(_w) {}
} e[200005];
int n, m;
bool cmp(Edge x, Edge y) {
    return x.w < y.w;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
    sort(e + 1, e + m + 1, cmp);
    d = DSU(n);
    long long ans = 0, cnt = n;
    for (int i = 1; i <= m; i++)
        if (!d.chk(e[i].u, e[i].v))
            d.unn(e[i].u, e[i].v), ans += e[i].w, cnt--;
    if (cnt != 1)
        printf("orz"); 
    else
        printf("%lld\n", ans);
    return 0;
}

Prim算法

思想

和 dijkstra 类似，我们把图中的 n 个点分到两个点集 U 和 V 中，初始时我们需要选一个起始点（其实选哪个都可以，因为最终会形成一个包含所有结点的生成树），我们可以选一号点，所以 U=\{1\},V=\{2,3,4,...,n\}。

我们设 d_i（i \in V）为 i 到 U 中的点的一条边的权值最小值，这个算法就是不断重复一下过程，直到 V=\varnothing ：

1) 选择 i 满足 i 是 V 中 d 最小的点，把这个点从 V 中删除，加入到 U 中，同时把答案加上 d_i。

2) 更新所有直接与 i 相连且在 V 中的点的 d 值。

最后当所有点都在 U 中即可结束，这是我们已经求出了答案。

很显然，这个算法也是贪心，所有我们依然需要证明一下它的正确性。

证明

假设我们不让 V 中 d 值最小的点 i 加入 U，而是让别的在 V 中的点 j 加入 U，因为最后 i 迟早要加入 U，所以最后就会变成这个样子：

所以我们发现如果把红边加上，黑边去掉，依然是一个生成树，且红边权值，根据我们的假设，是不大于黑边的，所以选红遍一定最好，得证。

实现

如果不加优化，总共需要 n-1 次把 V 中点加入 U，每次加入时去枚举以及更新的时间复杂度是 O(n) 的，所以总时间复杂度是 O(n^2)。

和 dijkstra 一样，prim 也能用优先队列优化，把时间复杂度降到 O(n \log m)，不过一般在正常的图中我们都会用 kruskal，只有在完全图中才会用 prim，而既然都在完全图了，所以 O(n^2) 就足以了，于是这个优化我就不放代码了，而且其实和 dijkstra 几乎一模一样。

代码：

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m;
int mtr[5005][5005] = {{0}};
int d[5005] = {0};
bool f[5005] = {false};
void Prim() {
    memset(d, 0x3f3f3f3f, sizeof d);
    long long ans = 0;
    d[1] = 0, f[1] = true;
    for (int i = 2; i <= n; i++)
        d[i] = min(d[i], mtr[1][i]);
    int cnt = 0;
    for (int i = 1; i < n; i++) {
        int pos = -1;
        for (int j = 1; j <= n; j++)
            if (!f[j] && (pos == -1 || d[pos] > d[j]))
                pos = j;
        if (pos != -1 && d[pos] != 0x3f3f3f3f)    
            f[pos] = true, ans += d[pos], cnt++;
        else
            break;
        for (int j = 1; j <= n; j++)
            if (!f[j] && mtr[pos][j] != 0x3f3f3f3f)
                d[j] = min(d[j], mtr[pos][j]);
    }
    if (cnt != n - 1)
        cout << "orz" << endl;
    else
        cout << ans << endl;
}
int main() {
    memset(mtr, 0x3f3f3f3f, sizeof mtr);
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v, w; i <= m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        mtr[u][v] = mtr[v][u] = min(mtr[u][v], w);
    }
    Prim();
    return 0;
}

最小生成树的性质

我们很容易就可以发现，一张图中的最小生成树不是唯一的，但是有一个性质：

同一张图的所有最小生成树中的权值为 w 的边的数量是相同的。

这个结论很有用，下面证明一下：

证明：

我们用数学归纳法，先假设同一张图的所有最小生成树中的权值小于 w 的边的数量都是相同的，在证 w 的情况。我们考虑 Kruskal 运行到第一条权值为 w 的边时，所有小于 w 的边已经都连完了。

我们假设存在一个最小生成树中权值 w 的边的数量为 a，同时另一个最小生成树中权值为 w 的边的数量为 b，其中 a<b。因为最小生成树中去掉任意一条边都会使得生成树不再是生成树，于是第一棵最小生成树中必然要多找 b-a 条权值比 w 大的边，才能形成生成树。

而既然第二棵最小生成树能选 b 条 w 的边，说明必然其中有一条边（就叫它 E_1）在 Kruskal 算法运行到此时是连接两个不同连通块的，而这条边在第一棵最小生成树中并不存在。为了使得这两个连通区域最终连通，必然还要有一条路径连接了这两个连通区域，把这条路径上某条边 E_2 去掉，再连上 E_1，此时最小生成树中依然有 n-1 条边且是连通的，于是这依然是一棵生成树。

但是 E_1 的边权小于 E_2，所以我们找到了一棵比第二颗最小生成树更小的生成树，与最小生成树的定义矛盾！所以绝对不可能存在两棵最小生成树中权值为 w 的边的数量不相同，证毕。

一些题目

北极通讯网络

题目链接：北极通讯网络

思路：

这题非常经典。我们考虑一下 k 台卫星设备意味着什么，因为任意两台卫星设备都可以直接对话，所以我们相当于只用把若干个村庄连成 k 个连通区域，给每个连通区域配一台卫星设备即可。

在 Kruskal 运行的时候，每新连一条边，连通块个数便减少一个，而前面已经证明过了， Kruskal 算法运行到任何时候答案都是最优的，于是我们只需要运行 Kruskal 算法直到连通块只剩 k 个即可。

有一个细节需要注意，这道题求的是最大的边权的最小值，但这是不是等同于最小生成树最大的一条边呢？答案是肯定的。因为同一张图中的最小生成树有一个性质：

同一张图中的所有最小生成树中权值为 w 的边的个数都是相同的。

这个前面已经证明了，于是就自然而然地推出了这个结论。

代码：提交记录

构造完全图

题目链接：构造完全图

思路：

也是很有趣的一道题。我们先把边按照边权从小到大排序，然后建立一个初始 n 个元素的并查集，并依次将边的两个端点所在连通区域合并，并更新答案。

考虑我们现在要把 x 和 y 两个连通区域用一条边权为 z 的边连起来，假设 x 和 y 已经是一个边权和最小的完全图了，我们为了使得最终的完全图只有这一棵最小生成树，我们可以把这两个连通区域的所有点所形成的完全图当中，所有还未被连上且不是我们现在选的这条边的边的边权全部复制为 z+1 即可。

这样 Kruskal 算法运行到这时一定会先选 z 这条边，因为这条边最小。

具体该怎么实现呢？其实很简单。我们在并查集合并时已经知道 x 和 y 的大小，于是我们只需要将答案加上：

(C_{sz_x+sz_y}^{2}-C_{sz_x}^2-C_{sz_y}^2)(z+1)

其实就是：

[\frac{(sz_x+sz_y)(sz_x+sz_y-1)-sz_x(sz_x-1)-sz_y(sz_y-1)}{2}](z+1)

所以就可以快乐的 AC 了~~~

代码：提交记录

秘密的牛奶运输

题目链接：秘密的牛奶运输

思路：

其实这道题就是要求严格次小生成树，即边权和严格大于最小生成树且小于其它所有生成树的生成树。

我们的方案是：次小生成树肯定至少有一条边与最小生成树不同，于是我们先求出最小生成树，然后枚举所有没被选过的边。设当前这条边是连接 u 和 v，权值为 w，则我们需要在 u 到 v 在最小生成树的简单路径上去掉一条边，用来加上这条边。

首先这条路径上所有的边权肯定都是小于等于 w 的（不然就不是最小生成树了），于是我们需要找出最大的且不等于 w 的边删去，这样依然是一棵生成树。次小生成树的边权和就是我们枚举完所有边后最小的答案。

但为什么这是对的呢？为什么不是重新找一棵与最小生成树完全不同的生成树呢？

请注意，这是有可能的，比如假设有一支球队 A 是所有球队中最厉害的，但是如果把 A 中的一名球员换掉，那 A 一定时第二厉害的吗？未必，毕竟足球讲究配合，第二强的球队完全有可能是一个和 A 从战术，球员组成等大相径庭的球队。

但是幸运的是，次小生成树是这样的。不然就没法求了

我们考虑重新跑 Kruskal 求最小生成树，只不过一开始我们先把本来不在最小生成树中的一条边连上了，因为次小生成树必然和最小生成树相差至少一条边，于是这样枚举所有未被选中的边，其中用这样的 Kruskal 跑出来的肯定有次小生成树。

整个过程中，除了 u 到 v 在生成树中的简单路径上的边，其他边的选取没有任何影响，还是和原来一样。而这条路径上必然有一条边是选不了的。既然有一条选不了，那肯定是要不选那条边权不等于 w 且是所有比 w 小的边中最大的的边，一个小小的贪心，于是这和我们之前的做法是一样的，且根据我们之前的推理，这其中必然有一棵次小生成树。

这个算法朴素时间复杂度是 O(nm) 的，而维护树上简单路径的最大和次大值是可以用倍增或树链剖分+线段树优化的，时间复杂度分别是 O(n \log n) 和 O(m (\log n)^2) 的，很明显倍增会快一点，但本人写这题时还不会倍增，所以写了线段树。

代码：提交记录

[NOIP2013 提高组] 货车运输

题目链接：[NOIP2013 提高组] 货车运输

思路：

一道大开眼界的题。本题几乎所有题解的做法都是求出最大生成树然后套各种高级数据结构，但其实这道题直接用并查集就可以做，并且时间复杂度是 O(q\log q) 的（貌似只有少数几篇题解提到了这种做法）。

我们可以把询问挂在点上，对于每个点都储存与这个点有关的所有询问，然后我们在跑 Kruskal 求最大生成树时，并查集中我们对于每个组代表维护这个组所有的询问，每次合并时我们按照询问的多少来作为秩来合并，并且把询问个数少的连通块的询问都处理了，对于每一个询问，如果另一边端点在另一个连通块中，直接统计答案，否则就把询问合并。

这样的时间复杂度是 O(q \log q) 的，这题 q 比较小，所以跑得飞快。

代码：提交记录

[国家集训队]Tree I

题目链接：[国家集训队]Tree I

思路：

这道题设计一个技巧。我们可以给所有黑边加上一个权值 w，其中 w 是一个整数（可以是负数），然后再求最小生成树。

但这又有什么用呢？我们可以发现，只要 w 越大，排序后黑边就会比较靠后，造成的结果就是白边选的数量多了，于是这样明显的单调性肯定是要二分啦。于是我们二分 w，而 \text{check(w)} 函数返回的就是当所有黑边都加上 w 时，最小生成树选的白边个数是否小于等于题目所求的个数，这很明显是一个左闭右开的区间，于是最终答案就是 \text{check(l)} 中求出的边权和减去 l \times ((n-1)-need)，即黑边加上的权值。

有一个细节，排序记得相同边权让黑色优先。

代码：提交记录

[JSOI2008]最小生成树计数

题目链接：[JSOI2008]最小生成树计数

思路：

一道题意很简单，但其实实现挺难的题。

还是那个结论，同一张图的所有最小生成树中的权值为 w 的边的数量是相同的，，而且题目说每种边不超过 10 条，于是乎我们可以对于每种颜色的边直接去子集枚举每种边的每条边选还是不选，这样时间复杂度是 O(2^{10}m)，稳过。

然后正当你开开心心以为你会了这道紫题时，你突然发现，子集枚举时需要有删除操作，就是把已经选了的某条边对并查集的影响删除，然后你就不会了。

所以这道题我们不能路径压缩，但是可以按秩合并。我们搞一个结构体记录每一次操作，代码如下：

struct Opr{//一次操作
    int i, pi, ti;//把p[i]从pi改为ti
    int j, pj, tj;//把sz[j]从pj改为tj
};

同时搞一个栈，用来存放所有已经做过的操作：

stack<Opr> st;

对于按秩合并，我们正常进行，不过要记录一下操作：

void unn(int a, int b) {//合并a,b所在分组;
    int pa = fnd(a), pb = fnd(b);
    if (p[pa] == p[pb]) 
        return;
    if (sz[pb] < sz[pa])
        swap(pa, pb);    
    st.push((Opr){pa, p[pa], p[pb], pb, sz[pb], sz[pb] + sz[pa]});
    cntCla--, sz[pb] += sz[pa], p[pa] = pb;
}

然后我们在搞一个回退操作，即把当前栈顶的操作撤销：

void rollBack() {//把st中的最后一个操作撤回
    p[st.top().i] = st.top().pi;
    sz[st.top().j] = st.top().pj;
    cntCla++, st.pop();
}

然后我们就可以正常的去做了。

代码：提交记录

[HNOI2006]公路修建问题

题目链接：[HNOI2006]公路修建问题

思路：

这道题很明显是二分答案，我们去二分最大的边权，然后对于所有满足边权小于等于当前的 mid 的边，然后我们看一下能不能先选 k 条已经公路，再选 (n-1)-k 条其他公路，如果能，说明这个答案是可行的；否则就是不行的。因为是求最大值最小，所以是左开右闭的区间。

代码：提交记录