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

最小割树 $\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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<bits/stdc++.h>
using namespace std;
typedef pair <int,int> Pii;
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

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
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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef pair <int,int> Pii;
#define reg register
#define pb push_back
#define mp make_pair
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

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;
	}
}