洛谷P3376【模板】网络最大流 ISAP

这篇博客写得非常好呀。

传送门

于是我是DCOI这一届第一个网络流写ISAP的人了，之后不用再被YKK她们嘲笑我用Dinic了！就是这样！

感觉ISAP是会比Dinic快，只分一次层，然后不能增广了再更新dis,再加上杂七杂八的优化，但是写起来要比Dinic稍微复杂一点点。

洛谷的模板比我改过后的Dinic又快了两倍多。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<queue>

#include<vector>

typedef long long LL;

const int maxn=,maxm=,INF=0x7f7f7f7f;

using namespace std;

int n,m,s,t,u,v,w,ecnt=,fir[maxn],d[maxn],cur[maxn],c[maxn],p[maxn];

struct edge {

    int from,to,cap,flow,nxt;

    edge(){}

    edge(int from,int to,int cap,int flow,int nxt):from(from),to(to),cap(cap),flow(flow),nxt(nxt){}

}e[maxm];

void add(int u,int v,int w) {

    e[++ecnt]=edge(u,v,w,,fir[u]);

    e[++ecnt]=edge(v,u,,,fir[v]);

    fir[u]=ecnt-; fir[v]=ecnt;

}

void init() {

    scanf("%d%d%d%d",&n,&m,&s,&t);

    for(int i=;i<=m;i++) {

        scanf("%d%d%d",&u,&v,&w);

        add(u,v,w);

    }

}

queue<int>que;

void bfs(int s,int t) {

    for(int i=;i<=n;i++) d[i]=n;

    d[t]=;

    que.push(t);

    while(!que.empty()) {

        int x=que.front() ;que.pop();

        for(int i=fir[x];i;i=e[i].nxt)

        if(d[e[i].to]==n&&e[i].flow==e[i].cap) {

            d[e[i].to]=d[x]+;

            que.push(e[i].to);

        }

    }

}

int cal(int s,int t) {

    int fl=INF;

    for(int x=t;x!=s;x=e[p[x]].from)

        fl=min(fl,e[p[x]].cap-e[p[x]].flow);

    for(int x=t;x!=s;x=e[p[x]].from) {

        e[p[x]].flow+=fl;

        e[p[x]^].flow-=fl;

    }

    return fl;

}

int Maxflow(int s,int t) {

    bfs(s,t);

    int res=;

    for(int i=;i<=n;i++) cur[i]=fir[i],c[d[i]]++;

    for(int x=s;d[x]<n;) {

        if(x==t) {

            res+=cal(s,t);

            x=s;

        }

        int ok=;

        for(int &i=cur[x];i;i=e[i].nxt)

            if(d[e[i].to]+==d[x]&&e[i].cap>e[i].flow){

                p[x=e[i].to]=i;

                ok=; break;

            }

        if(!ok) {

            cur[x]=fir[x]; int M=n;

            for(int i=cur[x];i;i=e[i].nxt)

                if(e[i].cap>e[i].flow)

                    M=min(M,d[e[i].to]+);

            if(!(--c[d[x]])) break;

            c[d[x]=M]++;

            if(x!=s) x=e[p[x]].from;

        }

    }

    return res;

}

void work() {

    printf("%d\n",Maxflow(s,t));

}

int main()

{

    init();

    work();

    return ;

}