最小割树 学习笔记 [网络流]

问题

luogu 4897 [模板] 最小割树(Gomory-Hu Tree)

给定一个 $n$ 个点 $m$ 条边的无向连通图,多次询问两点之间的最小割。

其中两点间的最小割是这样定义的:原图的每条边有一个割断它的代价,你需要用最小的代价使得这两个点不连通

$n \leqslant 500$, $m \leqslant 1500$ ,$q \leqslant 10^5$

方法

emmm……不证明的话很简单

首先有一个定理,就是一个n个点的图上,两点之间只有n种本质不同的最小割。因此一定存在一棵树,满足树上两点的最小割等于原图上两点的最小割。我们把这样的树称之为“最小割树”。 —Ebola

证明自然是没有的

在这里直接说建树方法,主要思想:分治

在图(当前点集)中任意选出来两个点 $s$ ,$t$,求出全图最小割 $flow(s,t)$,通过这条割将全图分成了两个连通块,其中 $s$ 所在的记作 $S$,$t$ 所在的记作 $T$。

引理: 对于任意的 $u \in S$,$v \in T$ ,都有 $flow(u,v) \leqslant flow(s,t)$

证明:如果不存在,则 $flow(s,t)$ 不足以割开 $s$ 和 $t$,因为 $u$,$v$ 依旧相连。

我们在最小割树上连一条 $s$,$t$ 之间的边,边权为 $flow(s,t)$。
然后再对 $S$ 和 $T$ 集合分治处理即可(做法同上)。

这样,我们分开 $n$ 个点跑了 $n$ 次网络流,建了 $n-1$ 条边,建成了一棵树,即最小割树。

时间复杂度 $n$ 次网络流 -> $O(n^3 m)$,但是由于 $Dinic$ 时间复杂度比较玄学(反正我不知道),跑不满,能过。

因为是对全图的网络流(不是残余网络),所以每次网络流前要先回复其(最大)流量

1
2
for(int i=2;i<=cnt;i++)
E[i].w=E[i^1].w=(E[i].w+E[i^1].w)>>1;

用处

自然是可以快速求出两点之间最小割的。

引理:对于图上两点 $u$,$v$,他们之间的最小割是他们在最小割树的路径上的边权最小值

求树上两点路径上边权的最小值,倍增和树剖都可以。

当然!因为点数相当的少(不然用不了),完全可以 $floyd$ 做到 O(1) 查询 懒人专用

代码

这模板咋 $500ms$ …… $O2$ 好哇

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
122
123
124
125
126
127
128
129
130
131
#include<bits/stdc++.h>
using namespace std;

namespace TYC
{
const int N=510;
const int M=1510;
const int inf=0x3f3f3f3f;

int s,t,n,m,cnt=1,Head[N],tmp[N],cur[N],arr[N],vis[N],dep[N],flow[N][N];

inline int read()
{
int x=0,f=0;char ch=getchar();
while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}

inline void write(int x)
{
int len=0;static int bask[50];
do bask[++len]=x%10,x/=10; while(x);
while(len) putchar('0'+bask[len--]);
putchar('\n');
}

struct edge
{
int to,next,w;
}E[M<<1];

inline void add(const int u,const int v,const int w)
{
E[++cnt]=(edge){v,Head[u],w};
Head[u]=cnt;
}

bool bfs()
{
queue<int> q;
memset(dep,0,sizeof(int[n+1]));
memcpy(cur,Head,sizeof(int[n+1]));
dep[s]=1,q.push(s);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=Head[u];i;i=E[i].next)
{
int v=E[i].to;
if(E[i].w&&!dep[v])
dep[v]=dep[u]+1,q.push(v);
}
}
return dep[t];
}

int dfs(const int u,const int mn)
{
if(u==t||!mn) return mn;
int v,w,used=0;
for(int &i=cur[u];i;i=E[i].next)
{
v=E[i].to;
if(E[i].w&&dep[v]==dep[u]+1)
{
w=dfs(v,min(mn-used,E[i].w));
used+=w;
E[i].w-=w,E[i^1].w+=w;
if(used==mn) return used;
}
}
if(!used) dep[u]=-1;
return used;
}

inline int Dinic()
{
int ans=0;
while(bfs()) ans+=dfs(s,inf);
return ans;
}

void search(const int u)
{
vis[u]=1;
for(int i=Head[u];i;i=E[i].next)
if(E[i].w&&!vis[E[i].to]) search(E[i].to);
}

void solve(const int l,const int r)
{
if(l==r) return;
s=arr[l],t=arr[r];
for(int i=2;i<=cnt;i+=2)
E[i].w=E[i+1].w=(E[i].w+E[i+1].w)>>1;
int f=Dinic();
memset(vis,0,sizeof(int[n+1]));
search(s);
for(int i=1;i<=n;i++) if(vis[i])
for(int j=1;j<=n;j++) if(!vis[j])
flow[i][j]=flow[j][i]=min(flow[i][j],f);
int t1=l,t2=r;
for(int i=l;i<=r;i++)
if(vis[arr[i]]) tmp[t1++]=arr[i];
else tmp[t2--]=arr[i];
memcpy(arr+l,tmp+l,sizeof(int[r-l+1]));
solve(l,t1-1),solve(t2+1,r);
}

void work()
{
n=read(),m=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read(),w=read();
add(u,v,w),add(v,u,w);
}
for(int i=1;i<=n;i++) arr[i]=i;
memset(flow,inf,sizeof(flow));
solve(1,n);
int q=read();
while(q--) write(flow[read()][read()]);
}
}

int main()
{
TYC::work();
return 0;
}

例题

[ZJOI2011] 最小割

luogu3329 bzoj2229

好像很多人用的都是二分+网络流,如果你知道最小割树的话,就可以用 $floyd$ 求出两点最小割之后直接查询了 so easy!

代码

代码是以前写的了

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

namespace TYC
{
const int MAXN=310,inf=0x3f3f3f3f;
int n,m,cnt,s,t,Head[MAXN],vis[MAXN],a[MAXN],cur[MAXN],dep[MAXN],flow[MAXN][MAXN],tmp[MAXN];

inline int read()
{
int x=0,f=0;
char ch=getchar();
while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}

struct edge
{
int to,next,w;
}E[2000010];

void add(int u,int v,int w)
{
E[++cnt]=(edge){v,Head[u],w};
Head[u]=cnt;
}

void init()
{
cnt=1;
memset(Head,0,sizeof(Head));
for(int i=1;i<=150;i++)
for(int j=1;j<=150;j++)
flow[i][j]=inf;
}

void clear()
{
for(int i=2;i<=cnt;i++)
E[i].w=E[i^1].w=(E[i].w+E[i^1].w)>>1;
}

bool bfs()
{
memset(dep,-1,sizeof(dep));
queue<int> q;
dep[s]=0;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=Head[u];i;i=E[i].next)
{
int v=E[i].to;
if(E[i].w&&dep[v]==-1)
dep[v]=dep[u]+1,q.push(v);
}
}
return dep[t]!=-1;
}

int dfs(int u,int mn)
{
if(u==t) return mn;
int w,used=0;
for(int &i=cur[u];i;i=E[i].next)
{
int v=E[i].to;
if(E[i].w&&dep[v]==dep[u]+1)
{
w=dfs(v,min(mn-used,E[i].w));
E[i].w-=w,E[i^1].w+=w;
used+=w;
if(used==mn) return used;
}
}
if(!used) dep[u]=-1;
return used;
}

int Dinic()
{
int ans=0;
while(bfs())
{
memcpy(cur,Head,sizeof(cur));
ans+=dfs(s,inf);
}
return ans;
}

void dfs1(int u)
{
vis[u]=1;
for(int i=Head[u];i;i=E[i].next)
{
int v=E[i].to;
if(E[i].w&&!vis[v]) dfs1(v);
}
}

void solve(int l,int r)
{
if(l==r) return;
s=a[l],t=a[r];
clear();
int f=Dinic();
//Tree: add_edge(s,t,f) 如果要建树
memset(vis,0,sizeof(vis));
dfs1(s);
for(int i=1;i<=n;i++) if(vis[i])
for(int j=1;j<=n;j++) if(!vis[j])
flow[i][j]=flow[j][i]=min(flow[i][j],f);
int L=l,R=r;
for(int i=l;i<=r;i++)
if(vis[a[i]]) tmp[L++]=a[i];
else tmp[R--]=a[i];
for(int i=l;i<=r;i++) a[i]=tmp[i];
solve(l,L-1),solve(R+1,r);
}

void work()
{
int T=read();
while(T--)
{
init();
n=read(),m=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read(),w=read();
add(u,v,w),add(v,u,w);
}
for(int i=1;i<=n;i++) a[i]=i;
solve(1,n);
int q=read();
while(q--)
{
int x=read(),ans=0;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(flow[i][j]<=x) ans++;
printf("%d\n",ans);
}
puts("");
}
}
}

int main()
{
TYC::work();
return 0;
}

参考资料

UranusITS的博客-最小割树