ISAP这的挺好学的,有了dicnic的思路之后,理解起来不难。

与dicnic相似的,ISAP一样要建分层图,但是ISAP只用建一次。

如何维护分层图呢?

有$d_x$表示$x$距离$t$的距离。

如果$x$没有了出度,即当前分层图中,流量到了$x$就进入了死胡同,出不去了。

为了让$x$的流量能出去,必然要改变$d_x$,增加$x$到$t$的距离。

增加多少取决于有现有流量的边$(x,y_i)$中,最小的$d_{y_i}+1$即为$d_x$

在代码实现中,可以以$d_x+1$的方式累加到$d_{y_i}+1$,并不影响答案。

再加上各种优化,比如弧优化,Gap优化等等,常数小的一匹,完爆dicnic。

关于Gap优化,实际上就是断层没断层,如果断层了,就没有增广路了。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
using namespace std;
const int M=1e5+5,N=1e5+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 edge{int y,c,next;}a[N<<1];int last[N],len,cur[N];
void ins(int x,int y,int c)
{
    a[++len]=(edge){y,c,last[x]};last[x]=len;
    a[++len]=(edge){x,0,last[y]};last[y]=len;
}
int gap[N],q[N],d[N],n,m,s,t;
void init()
{
    qr(n),qr(m);qr(s),qr(t);len=1;
    for(int i=1,x,y,c;i<=m;i++)qr(x),qr(y),qr(c),ins(x,y,c);
    memcpy(cur,last,sizeof cur);
    int l=1,r=1;q[1]=t;++gap[d[t]=1];
    for(int x=q[l],y;l<=r;++l,x=q[l])for(int k=last[x];k;k=a[k].next)if(!d[y=a[k].y])++gap[d[y]=d[x]+1],q[++r]=y;
}
ll flow(int x,int f)
{
    if(x==t)return f;
    ll fl=0;
    for(int &k=cur[x],y,tmp;k;k=a[k].next)if(d[x]==d[y=a[k].y]+1)
    {
        fl+=(tmp=flow(y,min(a[k].c,f)));
        f-=tmp;a[k].c-=tmp;a[k^1].c+=tmp;
        if(!f)return fl;
    }
    if(!(--gap[d[x]]))d[s]=n+1;
    ++gap[++d[x]];cur[x]=last[x];
    return fl;
}
int main()
{
    init();
    ll ans=0;
    while(d[s]<=n)ans+=flow(s,1e9);
    qw(ans);puts("");
    return 0;
}