预流推进的几种算法
Lagoon
2019-01-20 13:51:50
### 前言
本文介绍几个比较优秀的预流推进算法，包括朴素的ISAP算法，HLPP算法和自己脑补的LCT维护ISAP的算法。
### 警告：各种网络流算法的复杂度及其退化的可能性
Dinic算法及朴素的ISAP算法：$O(n^2 m)$ ，不加当前弧优化：$O(n m^2)$ 。
队列维护的的ISAP算法：$O(n^3)$ ，不加当前弧（或者叫允许弧）优化：$O(n^2 m)$ 。
HLPP算法：$ O(n^2 \sqrt m) $ ，不加当前弧（或者叫允许弧）优化：$O(n m \sqrt m)$ ，用堆维护优先队列：$ O(n^2 \sqrt m logn) $ 。
如果两者都是那就是$ O(nm \sqrt m logn) $。然而网上几乎所有代码都有这两个问题，这就是为什么很多预流推进的程序跑得还没Dinic快的原因。
LCT维护的ISAP算法： $O(nm logn)$ 但由于常数太大目前没有找到很好的用途。
##### 前置技能：
网络流的基本定义，Dinic算法，LCT（如果要看LCT维护ISAP的算法的话）。
## 朴素的ISAP算法
我们首先回忆一下Dinic算法的做法：每次从源点出发bfs出一个层次图，然后只在这个层次图上跑流。
而ISAP沿用了这种思想，但不同之处就是ISAP改为从汇点出发bfs出层次图，接下来动态维护这个层次图。
具体来说，ISAP首先bfs出每一个点和汇点的距离，寻找增广路时只沿着满足$d[u]=d[v]+1$ 的边 $u→v$（这样的边称为允许弧）走，如果找不到这样的边，说明这个点的距离“过时了”，需要重新找一个距离，而这个距离显然是当前残量网络中与点 $u$ 相邻的点 $v$ 中最小的 $d[v]+1$ ，即 $d[u]=min_{v,(u,v)∈E}d[v] +1$ 。而这样做的正确性也是显然的（可以参照Dinic算法）。
#### 复杂度证明：
首先，每一个点最多被重标号 $O(n)$ ，因为每个点与汇点的距离不超过 $n$ ，对于一次推流，我们把它分为“完全推流”（一次性流完整条边的容量），和“不完全推流”。
对于一次“完全推流”，我们知道，这条边 $(u,v)$ （包括它的反向边）可能再被推流当且仅当点 $u$ 或点 $v$ 被重标号。所以每一条边至多被“完全推流” $O(n)$ 次，而完全推流的总数为 $O(nm)$ 。
而对于一次增广，至少有一次“完全推流”，所以增广的次数也是 $O(nm)$ 的，而一次增广最多流 $O(n)$ 次，所以推流的总数是 $O(n^2m)$ 的。（但不存允许弧的话就会变成 $O(nm^2)$ ）
### ISAP的几个优化：
##### 1、当前弧/允许弧优化：
对于每一个点用领接表（开O2的话可以用vector）存它的允许弧，这样不用多余地访问不允许推流的边，而允许弧改变当且仅当一个点被重标号了，所以每次重标号的时候修改一下，这样是 $O(nm)$ 的，不影响程序整体效率。
##### 2、GAP优化：
开一个桶存每一个高度有几个点，重标号的时候看一下这个高度是否已经没有点了,如果是的话就不用再流了，因为这意味着图出现了断层。
### 代码：
（暂无，其实大家没必要去写朴素的ISAP，快来写下面的HLPP吧）
## HLPP算法
施工中。。。（等我期末考完吧）
### 代码：
```
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
#define re register
#define cmin(a,b) (a>(b)?a=(b):0)
#define cmax(a,b) (a<(b)?a=(b):0)
#define dmin(a,b) ((a)<(b)?(a):(b))
const int inf=1<<30,MaxN=10100,MaxM=121000;
struct edge{int to,v;edge*nx,*rec,*nx1;}e[MaxM<<1];edge*last[MaxN],*cur[MaxN],*cnt=e;
int h[MaxN],gap[MaxN],q[MaxN],n,s,t,n1,g[MaxN],nd[MaxN];
long long w[MaxN];
inline void addE(re int a,re int b,re int c)
{
*++cnt=(edge){b,c,last[a]};last[a]=cnt;cnt->rec=cnt+1;
*++cnt=(edge){a,0,last[b]};last[b]=cnt;cnt->rec=cnt-1;
}
inline void addV(re int a,re int h){nd[a]=g[h];g[h]=a;}
void bfs()
{
re int x,ta=2;q[1]=t;
memset(h,0,(n+1)<<2);h[t]=1;
for(re int i=1;i<ta;i++)
{
x=q[i];if(x==s)continue;
for(re edge*j=last[x];j;j=j->nx)if(!h[j->to])
h[j->to]=h[x]+1,q[ta++]=j->to;
}
}
void hlpp()
{
bfs();h[s]=n+1;re int ta=0,x,d;memset(w,0,(n+1)<<2);
for(re int i=1;i<=n;i++)
{
for(re edge*j=last[i];j;j=j->nx)if(h[j->to]==h[i]-1)
j->nx1=cur[i],cur[i]=j;
gap[h[i]]++;
}
for(re edge*j=last[s];j;j=j->nx)if(j->v&&h[j->to])
addV(j->to,h[j->to]),cmax(ta,h[j->to]),
w[j->to]+=j->v,j->rec->v=j->v,j->v=0;
while(ta)
{
x=g[ta];g[ta]=nd[x];nd[x]=0;
if(h[x]>n)continue;
for(re edge*&j=cur[x];j&&w[x];j=j->nx1)//推流
if(j->v&&h[j->to]==h[x]-1){
d=dmin(j->v,w[x]);if(!w[j->to]&&j->to!=t)
addV(j->to,h[j->to]),cmax(ta,h[j->to]);
j->v-=d,j->rec->v+=d;w[x]-=d;w[j->to]+=d;
if(!w[x])break;
}
if(w[x])//重标号
{
gap[h[x]]--;
if(!gap[h[x]])//gap优化
{
for(re int i=1;i<=n;i++)if(h[i]>h[x])gap[h[i]]=0,h[i]=n+1;h[x]=n+1;
while(ta&&!g[ta])ta--;continue;
}
h[x]=n+1;
for(re edge*j=last[x];j;j=j->nx)
if(j->v)cmin(h[x],h[j->to]+1);gap[h[x]]++;
for(re edge*j=last[x];j;j=j->nx)
if(j->v)if(j->v&&h[j->to]==h[x]-1)j->nx1=cur[x],cur[x]=j;
else if(j->rec->v&&h[j->to]==h[x]+1)j->rec->nx1=cur[j->to],cur[j->to]=j->rec;
addV(x,h[x]),cmax(ta,h[x]);
}while(ta&&!g[ta])ta--;
}
}
int main()
{
re int m,x,y,c;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(re int i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&c),addE(x,y,c);
hlpp();
printf("%lld\n",w[t]);
}
```
## LCT维护ISAP（口胡警告！！）
#### 前言
可能因为常数太大，太不实用了，我从来在网上没见过这个算法。只有维基上提了一下（只讲了复杂度，没有讲做法），于是我花了几天时间把它给脑补出来，也没有自己实现过。所以可能会有问题，有问题请帮忙指出一下。
#### 正文
让我们再回忆一下关于ISAP算法的复杂度，我们发现大部分时间都花在增广上面，而增广的实质是在找到一条路径的最小边权 $v$ ， $ans += v$ ，然后路径上的边权全部减去 $v$ ，接着进行重标号。
这样暴力做是 $O(n)$ 的，浪费了大量的时间，我们想想有没有能够快速维护这个操作的数据结构呢？
有！LCT！
我们从汇点以外所有点取出一条允许弧建成一颗树（这样做显然会建成树），然后我们的操作就变成了：
1、找到源点 $s$ 到汇点 $t$ 的链上的最小值 $v$ ， $ans+=v$ 。
2、源点 $s$ 到汇点 $t$ 的链上的所有边边权 $-= v$ 。
3、删除（cut掉）所有链上边权为 $0$ 的边。
4、对于所有“被删边的点”找到下一条允许弧link上了（这样操作完显然显然还会是树）。
5、若有点找不到“允许弧”，则重标号，cut掉所有指向它的边并执行步骤4。
（事实上3、4、5是同时执行的）
6、如果有一个点找不到“允许弧”，直接删除这个的并cut掉所有指向它的边，然后执行步骤4。
7、当图出现断层时，终止操作。
根据我在上面ISAP部分的证明，link和cut的次数都是 $O(nm)$ 的，所以总复杂度是 $O(nmlogn)$ 的。（然而LCT的常数啊。。。）
##### 关于反向边的处理：
显然地，一条边和它的反向边不可能同时为“允许弧”，所以我们只需要在cut掉一条边的时候再处理反向边就好了。
### 代码：
（暂无，可能得等挺久才会来填这个坑的吧。。。）