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

Posted on | Edited on | In | Views:

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

描述

给出一张 \(n\) 个点 \(m\) 条带权边的有向图，钦定一个根 \(r\)，求以 \(r\) 为根的最小有向生成树（树形图）。

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

下面给出的算法可以在 \(\mathcal O(n\times m)\) 的复杂度内求解，并且 Tarjan 提出了 \(\mathcal O(n\log n + 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\) 个点在最终的方案中恰好有一条入边，在第一步中选出的边若合法，必然是一种答案

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

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

我们可以把 \((u,v,w)\) 变成 \((u_0,v,w_0)\)

  • 新图如果仍然是合法的有向生成树，那么权值和不会变大，因此必然也是一种最小有向生成树
  • 不合法当且仅当在原来的最小有向生成树中 \(u_0\) 在 \(v\) 的子树中，即该边在原有向生成树中是返祖边，显然一个简单环不可能包含大于一条的返祖边，因此环上一定可以找出合法的未被取到的 \((u_0,v,w_0)\) 替换 \(v\) 原先的入边

而缩点后重构新图的边权显然需要把替换掉的环边的权值减去

这样最终得到的一定是一棵最小有向生成树，并且最小权值和就是每轮第一步选出的最小入边的权值总和

复杂度

排除了自环影响，除了最后一轮，每次重构的图都会至少减少一个点，单次复杂度 \(\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;
}