最大流isap

最大流

最大流问题，是网络流理论研究的一个基本问题，求网络中一个可行流f*，使其流量v(f)达到最大，这种流f称为最大流，这个问题称为(网络)最大流问题。最大流问题是一个特殊的线性规划问题，就是在容量网络中，寻找流量最大的可行流。（来自百度百科）

ISAP

ISAP是dinic算法的优化，把dinicO(n^2*m)优化到O(nm)，最重要的是ISAP比dinic短！ISAP比dinic短！ISAP比dinic短！（重要的事情说三遍）

Dinic算法中，我们需要每次搜索出层次图，而在ISAP中，我们只需要每次dfs的过程中修改距离标号。具体来说，我们用 $d [x]$

图解（虽然说也许看了图依然不懂，但应该还有一点用处的）

自己做的gif，不要骂制作烂。

代码（#101. 最大流（www.loj.ac））

#include<bits/stdc++.h>
#define inf (1ll<<57)
#define N 100009
#define M 1000009
#define int long long
using namespace std;
void read(int&n)
{
    int k=1;n=0;char ch=getchar();
    while(!('0'<=ch&&ch<='9')&&ch!='-')ch=getchar();
    if(ch=='-')k=-1,ch=getchar();
    while('0'<=ch&&ch<='9')n=n*10+ch-48,ch=getchar();
    n*=k;
}
int to[M],head[N],nxt[M],val[M],tot=1;
void add(int x,int y,int z){
    to[++tot]=head[x],nxt[tot]=y,val[tot]=z,head[x]=tot;
}
void adds(int x,int y,int z){add(x,y,z),add(y,x,0);}
int a[N],gap[N],hea[N],que[N],be,ed,s,t,x,y,z;
void init()
{
    memset(a,0,sizeof(a));
    memset(gap,0,sizeof(gap));
    memcpy(hea,head,sizeof(hea));
    ++gap[a[que[be=ed=1]=t]=1];
    while(be<=ed){
        x=que[be++];
        for(int i=head[x];i;i=to[i])
            if(!a[nxt[i]])
                ++gap[a[que[++ed]=nxt[i]]=a[x]+1];
    }
}
int n,m,ans;
int isap(int k,int fl)
{
    if(k==t)return fl;
    if(!fl)return 0;
    int tmp,flow=0;
    for(int&i=hea[k];i;i=to[i])
        if(a[k]==a[nxt[i]]+1&&(tmp=isap(nxt[i],min(fl,val[i]))))
        {
            flow+=tmp,fl-=tmp,val[i]-=tmp,val[i^1]+=tmp;
            if(!fl)return flow;
        }
    if(!(--gap[a[k]]))a[s]=n+1;
    ++gap[++a[k]],hea[k]=head[k];
    return flow;
}
signed main()
{
    read(n),read(m);
    read(s),read(t);
    for(int i=m;i;i--)
        read(x),read(y),read(z),adds(x,y,z);
    init();
    while(a[s]<=n)
     ans+=isap(s,inf);
    printf("%lld
",ans);
    return 0;
}