网络流Sap算法

GDKOi就快要开始了。没时间打解析，直接上模板。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int n,m;

struct EDGE

{

    int to,c;

    EDGE* las;

} e[1000001];

int cnt;

EDGE* last[1001];

#define rev(x) (e+(int(x-e)^1))

EDGE* cur[1001];

int h[1001];

int vh[1001];

int bz;

int sap_dfs(int,int);

int sap();

int main()

{

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

    int x,y,_c;

    while (n--)

    {

        scanf("%d%d%d",&x,&y,&_c);

        last[x]=&(e[cnt++]={y,_c,last[x]});

        last[y]=&(e[cnt++]={x,0,last[y]});

    }

    printf("%d\n",sap());

    return 0;

}

int sap_dfs(int x,int s)

{

    if (x==m)

        return s;

    EDGE* ei;

    int t,sum=0;

    for (ei=cur[x];ei;ei=ei->las)

    {

        cur[x]=ei;

        if (ei->c && h[x]==h[ei->to]+1)

        {

            t=sap_dfs(ei->to,min(s-sum,ei->c));

            sum+=t;

            ei->c-=t;

            rev(ei)->c+=t;

            if (s==sum)

                return s;

        }

    }

    cur[x]=last[x];

    if (!--vh[h[x]])

        bz=0;

    ++vh[++h[x]];

    return sum;

}

int sap()

{

    vh[0]=m;

    int flow=0;

    bz=1;

    while (bz)

        flow+=sap_dfs(1,2147483647);

    return flow;

}