最大流/最小割树/等价流树 学习笔记

Posted on Edited on In

最大流/最小割树/等价流树 学习笔记

最小割树 \(\text{Gomory-Hu Tree}\)

前置

约定无向图点数为 \(n\)，边数为 \(m\)。

割:断开一些边，使得 \(s,t\) 两点不连通。

设 \(\lambda(u,v)\) 为 \(u,v\) 的最小割权值。

在非负边权的无向图上使用网络流即可求得两点间的最小割，但是如果涉及查询所有点对的最小割，就需要进行 \(n^2\) 次网络流，复杂度很高。


简介

对于非负边权的无向图，适用于求出多点对之间的最小割/最大流的结构。

1.\(\text{Gomory-Hu Tree}\)的核心性质

构造树，使得树边 \((u,v)\) 满足割掉这条边后，\(u,v\) 的最小割对应将图分为树在两边的这两个集合。

而边 \((u,v)\) 的权值 \(w(u,v)=\lambda(u,v)\)。

2.求解最小割的方法

引理:

\(\lambda(a,b)\ge \min\{\lambda(a,c),\lambda(c,b)\}\)

证明：假设 \(\lambda(a,b) < \min\{\lambda(a,c),\lambda(c,b)\}\)

设 \(a,b\) 最小割的两个集合后两点所属的联通块集合为 \(A,B\)，则：

  1. 若 \(c\in A\)，则 \(a,b\) 最小割也是 \(b,c\) 的割。

  2. 若 \(c\in B\)，则 \(a,b\) 最小割也是 \(a,c\) 的割。

以上两种情况均与 \(\lambda(a,b) < \min\{\lambda(a,c),\lambda(c,b)\}\) 矛盾。


假设要求 \(u,v\) 两点间的最短路，则答案就是 \(u,v\) 在树上路径的最小边权值，设其为边 \((s,t)\)。

由上面的引理，显然有 \(\lambda(u,v)\ge\lambda(s,t)\)。

而我们由 \(\text{Gomory-Hu Tree}\) 的性质知道，\(s,t\) 的割也是 \(u,v\) 的一个割，即 \(\lambda(u,v)\le \lambda(s,t)\)。

所以答案就是 \(\lambda(s,t)\)。

构建方法

构建 \(\text{Gomory-Hu Tree}\) 最重要的一条引理，可以认为是最小割的"不交叉"性质

对于 \(s,t\) 最小割的一侧，设其点集为 \(W\)，则对于任意的 \(u,v\in W\)，存在一个 \(s,t\) 最小割 \(X\)，满足 \(X\sube W\)。

具体的证明比较复杂，咕，但是这个性质确实非常巧妙。

利用这个性质，可以得到 \(\text{Gomory-Hu Tree}\) 的不严谨的递归构造方法。

  1. 对于当前点集 \(S\)，若 \(|S|=1\)，则结束递归。

  2. 从 \(S\) 中选择两个点 \(x,y\) 求出最小割，设在割中 \(x,y\) 所属点集分别为\(X,Y\)。

  3. 在 \(\text{Gomory-Hu Tree}\) 上加入边 \((x,y,\lambda(x,y))\)，递归解决子问题 \(X\cap S,Y\cap S\)。


实际在递归求解 \(S\) 的问题时，应该将图中其他的点缩点（这是论文里说的，实际没有人这么写）。

是不是不缩点跑出来的树形是错的?

递归求解的次数为 \(O(n)\)，只需要求 \(O(n)\) 次网络流即可。

放一下丑陋的板子：

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

const int N=510,M=6200,INF=1e9+10;

int n,m;
int U[M],V[M],W[M];

struct Edge{
	int to,nxt,w;
} e[M];
int head[N],ecnt;
void AddEdge(int u,int v,int w) {
	e[++ecnt]=(Edge){v,head[u],w};
	head[u]=ecnt;
}
void Link(int u,int v,int w){ AddEdge(u,v,w),AddEdge(v,u,w); }
#define erep(u,i) for(int i=head[u];i;i=e[i].nxt)
int dis[N],vc,S,T;
void clear(){ rep(i,1,vc) head[i]=0; ecnt=1,vc=0; }
int Bfs() {
	rep(i,1,vc) dis[i]=INF;
	static queue <int> que;
	dis[S]=0,que.push(S);
	while(!que.empty()) {
		int u=que.front(); que.pop();
		erep(u,i) {
			int v=e[i].to,w=e[i].w;
			if(!w || dis[v]<=dis[u]+1) continue;
			dis[v]=dis[u]+1,que.push(v);
		}
	}
	return dis[T]<INF;
}
int Dfs(int u,int in) {
	if(u==T) return in;
	int out=0;
	erep(u,i) {
		int v=e[i].to,w=e[i].w;
		if(!w || dis[v]!=dis[u]+1) continue;
		int t=Dfs(v,min(in-out,w));
		e[i].w-=t,e[i^1].w+=t,out+=t;
		if(in==out) break;
	}
	if(!out) dis[u]=0;
	return out;
}
int Dinic(){
	int ans=0;
	while(Bfs()) ans+=Dfs(S,INF);
	return ans;
}

int Mincut(int u,int v){
	clear(),vc=n,S=u,T=v;
	rep(i,1,m) Link(U[i],V[i],W[i]);
	return Dinic();
}

vector <Pii> G[N];
int P[N],R[N];
void Build(int l,int r) {
	if(l==r) return;
	int x=P[l],y=P[l+1];
	int w=Mincut(x,y);
	int p1=l-1,p2=r+1;
	rep(i,l,r) if(dis[P[i]]<INF) R[++p1]=P[i];
	else R[--p2]=P[i]; 
	rep(i,l,r) P[i]=R[i];
	G[x].pb(mp(y,w)),G[y].pb(mp(x,w));
	Build(l,p1),Build(p2,r);
}

int fa[N][10],s[N][10],dep[N];

void dfs(int u,int f) {
	for(int i=1;(1<<i)<=dep[u];++i) fa[u][i]=fa[fa[u][i-1]][i-1],s[u][i]=min(s[u][i-1],s[fa[u][i-1]][i-1]);
	for(Pii t:G[u]) if(t.first!=f) {
		int v=t.first,w=t.second;
		fa[v][0]=u,s[v][0]=w,dep[v]=dep[u]+1;
		dfs(v,u);
	}
}

int LCA(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	int mi=1e9;
	for(int i=0,del=dep[x]-dep[y];(1<<i)<=del;++i) if(del&(1<<i)) cmin(mi,s[x][i]),x=fa[x][i];
	if(x==y) return mi;
	drep(i,9,0) if(fa[x][i]!=fa[y][i]) cmin(mi,s[x][i]),cmin(mi,s[y][i]),x=fa[x][i],y=fa[y][i];
	cmin(mi,s[x][0]),cmin(mi,s[y][0]);
	return mi;
}

int main() {
	n=rd()+1,m=rd();
	rep(i,1,m) U[i]=rd()+1,V[i]=rd()+1,W[i]=rd();
	rep(i,1,n) P[i]=i; Build(1,n);
	dfs(1,0);
	rep(kase,1,rd()) printf("%d\n",LCA(rd()+1,rd()+1));//printf("%d\n",MinCut(rd()+1,rd()+1));
}




等价流树

等价流树的树形不需要满足 \(\text{Gomory-Hu Tree}\) 的性质，只需要能够查询两点间的答案即可。

在论文中看到的等价流树的非递归构建方法（伪代码）。

\(w_{1,..,n}=0,fa_{1}=1,fa_{2,..,n}=1\)

\(\text{for u = 2 to n do}\) \(v = fa_u\)

求解\(u,v\)最小割

​ \(w_u=\lambda(u,v)\)

​ \(\text{for x=u+1 to n do}\)

​ \(\text{if} fa_x=v \text{ and x在u这一侧 then }fa_x=u\)

​ \(\text{end for}\)

\(\text{end for}\)

但是这个东西实际也不会跑得比 \(\text{Gomory-Hu Tree}\) 快，了解一下即可。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

const int N=860,M=170010,INF=1e9+10;

int n,m;
int U[M],V[M],W[M];

struct Edge{
	int to,nxt,w;
} e[M];
int head[N],ecnt;
void AddEdge(int u,int v,int w) {
	e[++ecnt]=(Edge){v,head[u],w};
	head[u]=ecnt;
}
void Link(int u,int v,int w){ AddEdge(u,v,w),AddEdge(v,u,w); }
#define erep(u,i) for(int i=head[u];i;i=e[i].nxt)
int dis[N],vc,S,T;
void clear(){ rep(i,1,vc) head[i]=0; ecnt=1,vc=0; }
int Bfs() {
	rep(i,1,vc) dis[i]=INF;
	static queue <int> que;
	dis[S]=0,que.push(S);
	while(!que.empty()) {
		int u=que.front(); que.pop();
		erep(u,i) {
			int v=e[i].to,w=e[i].w;
			if(!w || dis[v]<=dis[u]+1) continue;
			dis[v]=dis[u]+1,que.push(v);
		}
	}
	return dis[T]<INF;
}
int Dfs(int u,int in) {
	if(u==T) return in;
	int out=0;
	erep(u,i) {
		int v=e[i].to,w=e[i].w;
		if(!w || dis[v]!=dis[u]+1) continue;
		int t=Dfs(v,min(in-out,w));
		e[i].w-=t,e[i^1].w+=t,out+=t;
		if(in==out) break;
	}
	if(!out) dis[u]=0;
	return out;
}
int Dinic(){
	int ans=0;
	while(Bfs()) ans+=Dfs(S,INF);
	return ans;
}

int Mincut(int u,int v){
	clear(),vc=n,S=u,T=v;
	rep(i,1,m) Link(U[i],V[i],W[i]);
	return Dinic();
}

int fa[N],w[N];

int main() {
	n=rd(),m=rd();
	rep(i,1,m) U[i]=rd(),V[i]=rd(),W[i]=rd();
	rep(i,2,n) fa[i]=1;
	rep(u,2,n) {
		int v=fa[u]; w[u]=Mincut(v,u);
		rep(x,u+1,n) if(fa[x]==v && dis[x]==INF) fa[x]=u;
	}
}