虽然时间复杂度上看起来更优$O(n^2\sqrt{m})$,但是在随机图下,却没有ISAP快。

HLPP采用的也是分层图结构,不过它是实时流动,也就是实时更新分层图。

初始只有$s$的层次为$n$,其它待搜索,均为$0$

与ISAP相似的,如果一个点所携带的流量推不出去了,就改变它在分层图的层次,具体也就是在残存流量图中,与它相邻的点取最小的一个+1,就是它的层次。

同样可以使用Gap优化,来减少状态。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
using namespace std;
const int N=1e4+5,M=12e4+5;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;
    while(c<'0'||c>'9')c=gc;
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
}
void qw(int x)
{
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct node
{
    int x,d;
    node(int x=0,int d=0):x(x),d(d){}
    bool operator <(const node a)const{return d<a.d;}
};
struct heap
{
    node a[M];int len;
    void up(int j){for(int i=j>>1;j>1&&a[i]<a[j];j=i,i=j>>1)swap(a[i],a[j]);}
    void down(int i)
    {
        for(int j=i<<1;j<=len;i=j,j=i<<1)
        {
            if(j<len&&a[j]<a[j+1])++j;
            if(a[i]<a[j])swap(a[i],a[j]);
            else break;
        }
    }
    void push(node x){a[++len]=x;up(len);}
    void pop(){a[1]=a[len--];down(1);}
    bool size(){return len;}
    node top(){return a[1];}
}q;
struct edge{int y,next;ll c;}a[M<<1];int last[N],len;
void ins(int x,int y,ll c)
{
    a[++len]=(edge){y,last[x],c};last[x]=len;
    a[++len]=(edge){x,last[y],0};last[y]=len;
}
ll prs[N];int s,t,n,m,d[N],gap[N];
bool push(int x,int y,int k)
{
    ll tmp=min(a[k].c,prs[x]);
    a[k].c-=tmp;a[k^1].c+=tmp;prs[x]-=tmp;prs[y]+=tmp;
    return tmp;
}
void Gap(int l){for(int i=1;i<=n;i++)if(i!=s&&i!=t&&d[i]>l&&d[i]<=n)d[i]=n+1;}
ll maxflow()
{
    memset(prs,0,sizeof(prs));memset(d,0,sizeof(d));memset(gap,0,sizeof(gap));
    d[s]=n;prs[s]=1e12;q.push(node(s,d[s]));
    while(q.size())
    {
        node now=q.top();q.pop();
        int x=now.x;
        if(!prs[x])continue;
        for(int k=last[x],y=a[k].y;k;k=a[k].next,y=a[k].y)
            if((x==s||d[x]==d[y]+1)&&push(x,y,k)&&y!=t&&y!=s)q.push(node(y,d[y]));
        if(prs[x]&&x!=s&&x!=t)
        {
            if(!(--gap[d[x]]))Gap(d[x]);//加速结束
            ++gap[++d[x]];q.push(node(x,d[x]));
        }
    }
    return prs[t];
}
int main()
{
    len=1;
    qr(n),qr(m);qr(s),qr(t);
    for(int i=1,x,y,c;i<=m;i++)qr(x),qr(y),qr(c),ins(x,y,1ll*c);
    qw(maxflow());puts("");
    return 0;
}