预流推进的几种算法

· · 题解

前言

本文介绍几个比较优秀的预流推进算法，包括朴素的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掉一条边的时候再处理反向边就好了。

代码：

（暂无，可能得等挺久才会来填这个坑的吧。。。）