好久没写博客了，不过修了好多以前文章的锅。
描述
给出一张 $n$ 个点 $m$ 条带权边的有向图，钦定一个根 $r$，求以 $r$ 为根的最小有向生成树（Minimum Directed Spanning Tree，MDST，也即最小树形图）。
有向生成树（DST）即要求边是从父亲连向儿子。
下面给出的算法可以在 $O(n\times m)$ 的复杂度内求解，另外存在更优的算法。
算法
学习自 这里。
流程
自环可以特判，重边没有影响。
1
除了根节点，对每个点 $i$ 找到一条边权最小的入边，如果有多条相同，可以任意选择。
记 $a_i$ 表示这条入边的起点，$b_i$ 表示这条边的边权。
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 取到了这个环上的除一条边以外的全部边”。
复杂度
排除了自环影响，除了最后一轮，每次重构的图都会至少减少一个点，单次复杂度 $O(m)$，因此总复杂度 $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
做法
这题没有钦定一个根，我们可以新建一个根，连极大的边到每个点，保证了如果原图有解极大边只会取一次。
新图必然是有解的，原图无解即极大边选取了多次，判一下就好了。
时间复杂度还是 $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;
}
|