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

Posted on | Edited on | In | Views:

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

描述

给出一张 \(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;
}
0%