0%

最小树形图 朱刘算法学习笔记

好久没写博客了,不过之前文章的锅修了好多

描述

给出一张 $n$ 个点 $m$ 条带权边的有向图,钦定一个根 $r$,求以 $r$ 为根的最小有向生成树(Minimum Directed Spanning Tree,MDST,也即最小树形图)。

有向生成树(DST)即要求边是从父亲连向儿子

下面给出的算法可以在 $\mathcal O(n\times m)$ 的复杂度内求解,另外存在更优的算法

算法

学习自 这里

流程

自环可以特判,重边没有影响

1

除了根节点,对每个点 $i$ 找到一条边权最小的入边,如果有多条相同,可以任意选择

记 $a_i$ 表示这条入边的起点,$b_i$ 表示这条边的边权

2

  1. 如果所选的边形成一棵树,结束

否则会形成若干环套树外加包含根节点的一棵树

  1. 如果此时有根节点以外的孤立的点,则无法形成合法的有向生成树,结束

  2. 把每个环缩成一个点,不在环上的点保留,设点 $u$ 所属的环在新图中的编号为 $id_u$ 对于一条两端不在同一个环内的边 $(u,v,w)$,变成 $(id_u,id_v,w-b_{id_v})$

形成的新图重复该步骤

3

最小权值和就是每轮第一步选出的最小入边的权值总和

如果题目需要,可以复原出选择的边

理解及证明

除了根节点外的 $n-1$ 个点在 MDST 中恰好有一条入边,因此如果在第一步中选出的边合法,则必然是最小的,可以得到 MDST

否则考虑一个环,环上至少有一个点的入边需要调整,可以证明存在一个 MDST 取到了这个环上的除一条边以外的全部边

对于任意一个 MDST,如果有一个环多于一条边未取到,那么考虑环上的一条未被取到的边 $(u_0,v,w_0)$,假设对于 $v$ 在方案中选取的边是 $(u,v,w)$,由于环是最小的,那么有 $w_0\le w$

我们可以尝试把 $(u,v,w)$ 改成环边 $(u_0,v,w_0)$

  • 新图如果仍然是合法的 DST,那么权值和不会变大,因此必然也是一个 MDST
  • 出现不合法当且仅当在原来的 MDST 中 $u_0$ 在 $v$ 的子树中,即该边在原有向生成树中是返祖边。而如果一个环需要换边,其必有一条不是返祖边的非树边,因此上述操作可以不断执行直到满足“MDST 取到了这个环上的除一条边以外的全部边”

复杂度

排除了自环影响,除了最后一轮,每次重构的图都会至少减少一个点,单次复杂度 $\mathcal O(m)$,因此总复杂度 $\mathcal O(n\times m)$

代码

参考下面的例题一

例题

好像都是板子

例题一 LOJ #140. 最小树形图

LOJ #140. 最小树形图

模板

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
const int N = 105, M = 10005;
int n, m, r, p, ans, mm, id[N], a[N], b[N], x[M], y[M], z[M];
bool instk[N], vis[N];
void dfs(int u){
if(u==r) return;
instk[u]=vis[u]=1;
if(!vis[a[u]]) dfs(a[u]);
else if(instk[a[u]]){
id[u]=++p;
for(int j=a[u]; j!=u; j=a[j]) id[j]=p;
}
instk[u]=0;
if(!id[u]) id[u]=++p;
}
int main() {
scanf("%d%d%d", &n, &m, &r);
for(int i=1; i<=m; ++i) scanf("%d%d%d", x+i, y+i, z+i);
while(1){
for(int i=1; i<=n; ++i) b[i]=1e9;
for(int i=1; i<=m; ++i) if(z[i]<b[y[i]]) b[y[i]]=z[i], a[y[i]]=x[i];
memset(id+1, 0, n<<2), memset(vis+1, 0, n), id[r]=p=1;
for(int i=1; i<=n; ++i) if(i!=r){
if(b[i]==1e9) return puts("-1"), 0; else ans+=b[i];
if(!vis[i]) dfs(i);
}
if(p==n) break;
mm=0;
for(int i=1; i<=m; ++i) if(id[x[i]]!=id[y[i]])
z[++mm]=z[i]-b[y[i]], x[mm]=id[x[i]], y[mm]=id[y[i]];
m=mm, n=p, r=id[r];
}
return printf("%d", ans), 0;
}

例题二 LOJ #6510. 「雅礼集训 2018 Day8」A

LOJ #6510. 「雅礼集训 2018 Day8」A

做法

这题没有钦定一个根,我们可以新建一个根,连极大的边到每个点,保证了如果原图有解极大边只会取一次。

新图必然是有解的,原图无解即极大边选取了多次,判一下就好了

时间复杂度还是 $\mathcal O(n\times m)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<string.h>
#include<cmath>

using namespace std;
#define ll long long

const int N = 505, M = 126000;
int n, m, p, mm, id[N], a[N], x[M], y[M];
ll ans, b[N], z[M];
bool vis[N], instk[N];
void dfs(int u){
if(!u) return;
instk[u]=vis[u]=1;
if(!vis[a[u]]) dfs(a[u]);
else if(instk[a[u]]){
id[u]=++p;
for(int i=a[u]; i!=u; i=a[i]) id[i]=p;
}
instk[u]=0;
if(!id[u]) id[u]=++p;
}
int main() {
scanf("%d%d", &n, &m);
for(int i=1; i<=m; ++i) scanf("%d%d%lld", x+i, y+i, z+i);
for(int i=1; i<=n; ++i) y[++m]=i, z[m]=1ll<<40;
while(1){
for(int i=1; i<=n; ++i) b[i]=1ll<<50;
for(int i=1; i<=m; ++i) if(z[i]<b[y[i]]) b[y[i]]=z[i], a[y[i]]=x[i];
memset(vis+1, 0, n), memset(id+1, 0, n<<2), mm=p=0;
for(int i=1; i<=n; ++i){
ans+=b[i];
if(!vis[i]) dfs(i);
}
if(n==p) break;
for(int i=1; i<=m; ++i) if(id[x[i]]!=id[y[i]])
z[++mm]=z[i]-b[y[i]], x[mm]=id[x[i]], y[mm]=id[y[i]];
m=mm, n=p;
}
return printf("%lld", ans>(2ll<<40)?-1:ans-(1ll<<40)), 0;
}