网络流——最大流算法ISAP

Date:2023.1.12

简介

ISAP 和 dinic 十分相似,应该比较好懂

GAP 则是 ISAP 的优化

ISAP

ISAP 算法,也是运用 bfs分层+dfs搜索

与 dinic 区别有两点:

1.只用了一次 bfs 分层,后续层数更新随着 dfs 一起

2.因为某些原因(dfs 更新层数),dfs 需要反跑(汇点->源点)

过程

因为 ISAP 的 dfs 需要反跑,知道大家肯定打不习惯

于是,我们可以反跑 bfs分层,就可以正跑 dfs(反跑时汇点层数为 0)

dfs 时,过程与 dinic 基本相同,这里不详细展开

主要说如何更新层数:

更新层数

\(i\) 点的层数为 \(d_i\)

当我们结束了一次 dfs(没有路可走),我们就要更新层数

遍历 \(i\) 的所有连点 \(\left ( c>f \right)\),找到连点中最小的层数,设为 \(d_j\)

\(d_i=d_j+1\)

若点 \(i\) 没有连点,令 \(d_i=n\)

另外,我们不难发现,当 \(d_s\ge n\),增广路已被搜完,结束循环

优化

当前弧优化

时间复杂度:\(\color{orange}O\left(n^2m\right)\)

GAP

在 ISAP 算法的基础上,我们加一个数组 \(num\)

\(num_i\) 表示层数为 \(i\) 的点有多少个

更新层数时同时也更新 \(num\)

若一次更新后,\(num_i=0\),说明图中出现断层,不需要再搜索,直接退出

时间复杂度:\(\color{orange}O\left( \le n^2m \right)\)

特别说明:

SAP 的复杂度是 \(\color{orange}O\left(n^2m\right)\)

但 GAP 优化较不稳定(但一定小于\(\color{orange}n^2m\)),给 ISAP 的复杂度带来较大的向下浮动

所以, ISAP 和 dinic 哪个更优就十分奇妙了

建议:

小数据可用 dinic

大数据用 ISAP

当然,也可以打两个,测一下哪个更优

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
#include<bits/stdc++.h>
#define N 1205
#define M 120005
using namespace std;
int n,m,s,t;
int tot=1,to[M*4],nt[M*4],tmp[M*2];
int pre[M*2],ppre[M*2];
int cur[M*2],num[M*2];
long long ans,sum=0x3f3f3f3f3f3f3f3f,f[M*4],c[M*4];
void add(int x,int y,int u,int uu){
to[++tot]=y;
nt[tot]=tmp[x];
tmp[x]=tot;
c[tot]=u;
f[tot]=uu;
}
long long min(long long aa,long long bb){
return aa<bb?aa:bb;
}
int qe[M*2],head,tail;
int dep[M];
bool vis[M],oo[205][205];
void bfs(){
for(register int i=0;i<=M;i++) vis[i]=0;
head=tail=0;
dep[t]=0;
qe[++tail]=t;
vis[t]=1;
cur[t]=tmp[t];
num[0]=1;
while(head<tail){
int x=qe[++head];
for(register int i=tmp[x];i;i=nt[i]){
int u=to[i];
if(!vis[u]&&c[i^1]>f[i^1]){
cur[u]=tmp[u];
dep[u]=dep[x]+1;
vis[u]=1;
qe[++tail]=u;
num[dep[u]]++;
}
}
}
}
int main(){
//freopen("gap.in","r",stdin);
scanf("%d%d%d%d",&n,&m,&s,&t);
int xx,yy,zz;
for(register int i=1;i<=m;i++){
scanf("%d%d%d",&xx,&yy,&zz);
add(xx,yy,zz,0),add(yy,xx,0,0);
}
int x=s;
bfs();
for(register int i=1;i<=n;i++) cur[i]=tmp[i];
while(dep[s]<n){
if(x==t){
ans+=sum;
for(register int i=t;i!=s;i=pre[i]){
f[ppre[i]]+=sum;
f[ppre[i]^1]-=sum;
}
x=s;
sum=0x3f3f3f3f3f3f3f3f;
}
bool flag=0;
for(register int i=cur[x];i;i=nt[i]){
int u=to[i];
if(c[i]>f[i]&&dep[x]==dep[u]+1){
flag=1;
pre[u]=x,ppre[u]=i;
cur[x]=i;
sum=min(sum,c[i]-f[i]);
x=u;
break;
}
}
if(!flag){
int y=n-1;
for(register int i=tmp[x];i;i=nt[i]){
int u=to[i];
if(c[i]>f[i]) y=min(y,dep[u]);
}
--num[dep[x]];
dep[x]=y+1;
num[dep[x]]++;
if(num[dep[x]]==0) break;
cur[x]=tmp[x];
if(x!=s) x=pre[x];
}
}
printf("%lld",ans);
return 0;
}

参考:oi-wiki