最小生成树

简介

= =

关于最小生成树的一些理解

首先我们定义在一棵树里添加一条边，然后在产生的环中去掉一条边的操作叫做换边

对于任意两棵生成树，一定可以通过换边操作是其中一棵生成树变成另一棵生成树

性质1：将一棵树中的所有边的权值按从小到大的顺序排列形成的列表称为有序边权列表，则任意两棵最小生成树的有序边权列表是相同的

证明：设最小生成树有 $n$ 条边，不妨将两棵最小生成树分别称为 $A$，$B$，如果 $e$ 是一条边，令 $w(e)$ 为这条边的权值

令 $A$ 的边按照权值排序之后为 $a_i$，$B$ 的边按照权值排序之后为 $b_i$

令 $k$ 为两个边列表中，第一次出现 $a_k\neq b_k$ 的位置，不妨假设 $a_k\ge b_k$

这时我们分两种情况讨论：

$A$ 中包含 $b_k$，则一定有 $p>k$，使得 $a_p=b_k$，那么我们又 $w(b_k)=w(a_p)\ge w(a_k) \ge w(b_k)$，那么实际上我们有 $w(a_k)=w(b_k)=w(a_p)$，那么我们交换 $a_k$ 和 $a_p$ 并不会影响 $A$ 的有序边权列表
$A$ 中不包含 $b_k$，那么我们尝试将 $b_k$ 加入到 $A$ 中，形成一个环，由于 $A$ 是最小生成树，则这个环上任意一条边的权值都小于等于 $w(b_k)$，另外这个环中一定存在至少一条边 $a_p$ 不属于 $B$，因此我们有 $w(a_p)\le w(b_k)$，且 $p>k$，因为 $a_p$ 不在 $B$ 中，所以我们有 $w(a_p)\ge w(a_k)\ge w(b_k)$ 以及 $w(a_p)\le w(b_k)$，所以 $w(a_p)=w(a_k)=w(b_k)$。那么我们用 $b_k$ 替换 $a_p$ 并不会影响 $A$ 的有序边权列表

性质2：图 $G$ 中不存在一棵最小生成树包含 $G$ 中一个环上权值最大的所有边

证明：假设存在一棵最小生成树 $T$ 包含 $G$ 中某个环上权值最大的所有边，我们不妨在其中选择一条，将其去掉后，树 $T$ 变成两个连通块，不妨令其为 $A,B$，对于这个环，一定还有另一条边连接 $A$ 和 $B$，由于这条边之前不在树 $T$，它的权值一定小于最大权值，我们将其加入后，形成的新生成树 $T’$ 的权值变小，矛盾

特别的，如果一个环中的权值的最大的边唯一，则最小生成树一定不会包含这条边

性质3：对于一棵最小生成树 $A$，$A$ 可以通过若干次换边操作得到另一棵最小生成树 $B$，只需要保证每次换边之后 $A$ 仍然是一棵最小生成树即可

首先由性质 $1$ 可以得到一种换边方法，但是实际上有性质 $2$，我们可以得到一种更加通用的换边方法，每次选择一条 $B$ 中存在，$A$ 中不存在的边，在形成的环中，至少有一条与这条新加的边的权值相同且不在 $B$ 中的边

稍微证明一下，如果没有与新加的这条边权值相同的边，那么就是说 $B$ 包含一个环上权值最大的所有边，与性质 $2$ 矛盾

如果所有与新加的边权值相同的边都在 $B$ 中，同样说名 $B$ 包含一个环上权值最大的所有边，与性质 $2$ 矛盾

性质4：对于一棵最小生成树 $A$，它的有序边权列表的字典序是最小的，反之也成立

证明：

性质5：一棵树不是最小生成树，则一定存在一个换边操作，使得操作后它的总权值变小

算法

Kruskal

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

int fa[maxn];
void init_fa() { for (int i = 1; i <= n; ++i) fa[i] = i; }

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int mst; 
void kruskal() {
    sort(e + 1, e + m + 1); mst = 0; 
    for (int i = 1; i <= m; ++i) {
        int u = e[i].fr, v = e[i].to, w = e[i].w, fu = find(u), fv = find(v);
        if (fu == fv) continue;
        fa[fu] = fv; mst += w;
    }
}

Prim

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

struct Queue {
    int k, v;

    Queue() {}
    Queue(int _k, int _v) { k = _k; v = _v; }

    friend bool operator < (cQ &u, cQ &v) { return u.v > v.v; } 
}; int dis[maxn], s, mst; bool vis[maxn]; 
priority_queue<Queue> Q; 
void Prim() {
    memset(dis, 127, sizeof dis); dis[s] = 0; Q.push(Queue(s, 0)); 
    while (!Q.empty()) {
        int u = Q.top().k, _w = Q.top().v; Q.pop(); 
        if (vis[u]) continue; vis[u] = 1; mst += _w; 
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            if (dis[v] > w) {
                dis[v] = w;
                Q.push(Queue(v, dis[v]));
            }
        }
    }
}

Boruvka

大概就是每一轮对于每个连通块找到最小的一条连接别的连通块的边，然后合并这两个连通块

由于每次连通块的个数都会减半，所以时间复杂度为 $O(m\log n)$

int ans, a[maxn];
void Boruvka() {
    int cnt = n; init_fa(); e[0].w = INF; 
    while (cnt > 1) {
        fill(a, a + maxn, 0);
        for (int i = 1; i <= m; ++i) {
            int u = e[i].fr, v = e[i].to, w = e[i].w, fu, fv;
            if ((fu = find(u)) == (fv = find(v))) continue;
            if (e[a[fu]].w > w) a[fu] = i;
            if (e[a[fv]].w > w) a[fv] = i; 
        }
        for (int i = 1; i <= n; ++i) {
            if (!a[i]) continue;
            int u = e[a[i]].fr, v = e[a[i]].to, w = e[a[i]].w, fu, fv;
            if ((fu = find(u)) == (fv = find(v))) continue;
            --cnt; fa[fu] = fv; ans += w; 
        } 
    }
}

性质

同一个图不同的最小生成树中，每种权值的边的出现次数是相同的
不同的最小生成树中，某一种权值的边连接完成后，形成的连通块状态是一样的

例题

简要题意：给定一个长度无限大，宽度为 $m$ 的平面，现在我们依次在平面上加入 $n$ 个点，每加入一个点都需要求一个最小的半径 $r$，使得平面上这些点变成半径为 $r$ 的圆后，这些圆的并将平面封住，即无法从平面最左侧走到最右侧

$n\le 2000$

简要题解：我们考虑如果机器人的半径是 $r$ 会发生什么

以每个家具为圆心画半径为 $r$ 的圆，机器人的圆心不能在这个园内

那么我们考虑如果家具的圆将上下封住机器人就没法走了

所以我们以家具之间的距离为边的长度建图，然后跑最小生成树即可

注意到要求 $n$ 次最小生成树，且每次需要加 $O(n)$ 条边

但实际上我们每次只需要保留上一棵树的树边，与新加的边一起跑 $kruskal$ 即可

时间复杂度 $O(n^2\log n)$

校内赛 T4 扫地机器人
简要题意：给定一个有 $n$ 个点 $m$ 条边的无向图，边有黑白两种颜色，要求一棵有 $k$ 条白边的生成树，且该树的最长边的权值最小

$n\le 10^5,m\le 2\times 10^5$

简要题解：我们考虑二分答案

然后我们先加白边，这样可以求出最多有 $R$ 条白边

然后先加黑边，这样可以求出最少有 $L$ 条白边

如果 $L\le k\le R$，则一定有一颗只含有 $k$ 条白边的生成树

简单证明：我们考虑有 $R$ 条白边的生成树可以通过换边操作换成有 $L$ 条白边的生成树

2020年广西省CCPC大学生程序设计竞赛 B Longest Road
每次查询删除一条边之后的最小生成树

bzoj 2238 Mst 维护每条非树边能替换哪些树边
简要题意：给定一个 $n$ 个点 $m$ 条正权边的无向连通图，同时再给定一条边 $(u,v,w)$，求最少删除多少条边才能使这条边既有可能出现在最小生成树上，也有可能出现在最大生成树上

$n\le 20000,m\le 2\times 10^5$

简要题解：我们考虑对于一条边 $(u,v,w)$，它怎样才可能出现在最小生成树上

显然是当添加完边权小于 $w$ 的边之后，$u$ 和 $v$ 仍然不连通

也就是说我们只需要求一个以 $u$ 为源点，$v$ 为汇点的最小割即可

对于最大生成树，我们只需要把边权大于 $w$ 的边拿出来做一遍即可

两次答案相加就是最终答案

Luogu P5934 [清华集训2012]最小生成树
边有黑白两种颜色，求恰好有 $k$ 条白边的最小生成树

Luogu P2619 [国家集训队]Tree I

带权二分
简要题意：给定 $n$ 个点完全图，第 $i$ 个点的权值是 $a_i$，对于连接 $(u,v)$ 边，它的权值是 $a[u]~xor~a[v]$ 求最小生成树

$n\le 2\times 10^5$

简要题解：我们考虑 $kruskal$ 按照边的权值加边

我们考虑利用 $01Trie$ 的分治过程，对于分治的左右部分，因为每个部分内部的边的权值一定小于跨过两边的权值，所以内部肯定已经练好，为了将两边连接，我们只需要找一条最小的边即可，这个可以用 $01Trie$ 来做

时间复杂度 $O(n\log^2 n)$

CF 888G Xor-MST
简要题意：给定一个长度为 $n$ 的序列 $a_i$，$a_i$ 互不相同，定义两个点 $(x,y)$ 的距离为 $popcount(a_x,a_y)$，求最小生成树

$n\le 2\times 10^5,a_i< 2^{18}$

简要题解：我们考虑建一张有 $2^{18},[0,2^{18}-1]$ 个点的图，点 $u$ 的出边为 $u\oplus 2^{i},i\in[0,17]$，我们令 $a_i$ 为关键点，然后进行多源点 $bfs$，对于每个点 $u$，我们记录离它最近的关键点 $id_u$，然后对于每个与它相连的点 $v$，我们记录一条连接 $(id_u,id_v)$ 的边，然后拿这些边跑 $kruskal$ 即可，注意到这样一定是正确的，因为如果有若干个关键在某个非关键点进行合并的话，离这个非关键点最近的那个点一定会参与合并，所以我们只记录它就行了

时间复杂度 $O(18n\log (18n))$

The 14th Chinese Northeast Collegiate Programming Contest A Micro Structures Thread

转成求最小生成树

给定一个 $n\times m$ 的棋盘，染每个格子都有一个代价 $cost_{i,j}$，对于任意一个矩形边框，如果三个角已经被染色，那么第四个角将自动被染色

求最小代价等价于将行和列全部连通，所以直接求最小生成树

2021牛客多校3 B Black and white
简要题意：给定一张 $n$ 个点 $m$ 条边的无向图，现在要求将这 $n$ 个点分成两个点集，一个点集的权值为点集内的点之间的边的权值的最大值，现在要求一种分法，使得两个点集的权值的最大值最小

$n\le 2\times 10^4,m\le 10^5$

简要题解：我们考虑按照边权从大到小加入边，对于现在加入的边 $(u,v)$，如果 $u$ 和 $v$ 没有连通，那么我们将这条边加入，然后将 $u$ 和 $v$ 划分到不同集合，如果 $u$ 和 $v$ 已经连通，那么如果 $u$ 和 $v$ 在同一个集合，那么答案就是这条边的权值，否则什么都不做

我们发现这就是求最大生成树的过程，也就是说，最大生成树上相邻的两个点在不同集合，那么我们得到了划分方案，根据这个方案计算答案即可

Luogu P1525 [NOIP2010 提高组] 关押罪犯(最小生成树)
简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在要将每个数划分到两个集合，一个几何的权值为集合内的所有数，两两之间的异或和的最小值，现在要求一种分法，使得两个点集的权值的最小值最大

$n\le 10^5$

简要题意：参照Luogu P1525 [NOIP2010 提高组] 关押罪犯(最小生成树)即可

The 2020 ICPC Asia Macau Regional Contest C Club Assignment

简介

关于最小生成树的一些理解

算法

Kruskal

Prim

Boruvka​

性质

例题

转成求最小生成树

Boruvka