我的 ISAP 模板

题目： http://poj.org/problem?id=1273

分析：最大流模板题（用于测试模板）

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf_int = 1e9;
const int maxn = 5+200;
int n,m;
struct EDGE
{
    int en,next,f;
}E[2*1000000];
int T,p[maxn];
inline void addEDGE(int st,int en,int f)
{
    E[T].en=en, E[T].f=f, E[T].next=p[st], p[st]=T++;
    swap(st,en), f=0;
    E[T].en=en, E[T].f=f, E[T].next=p[st], p[st]=T++;
}
int start,end;
int dis[maxn],gap[maxn],cur[maxn],pre[maxn];
int ISAP(int n)
{
    memset(dis, 0, sizeof dis);
    memset(gap, 0, sizeof gap); gap[0]=n;
    memcpy(cur, p, sizeof p);
    pre[start] = -1;
    int e,a=start,maxflow=0,aug=inf_int;
    while(dis[start] < n)
    {
        for(e=cur[a]; e+1; e=E[e].next)
            if(E[e].f && dis[a]==dis[E[e].en]+1)
                break;
        if(e+1)
        {
            aug = min(aug, E[e].f);
            cur[a] = e;
            pre[E[e].en] = a;
            a = E[e].en;
            if(a == end)
            {
                for(a=pre[a]; a+1; a=pre[a])
                {
                    E[cur[a]].f -= aug;
                    E[cur[a]^1].f += aug;
                }
                maxflow += aug;
                aug = inf_int;
                a = start;
            }
        }
        else
        {
            if(--gap[dis[a]] == 0)
                break;
            int mind=n;
            for(e=p[a]; e+1; e=E[e].next)
                if(E[e].f && mind > dis[E[e].en])
                {
                    mind = dis[E[e].en];
                    cur[a] = e;
                }
            dis[a] = mind+1;
            gap[dis[a]]++;
            if(a != start)
                a = pre[a];
        }
    }
    return maxflow;
}
int main()
{
    int st,en,flow;
    while(scanf("%d %d", &m,&n)+1)
    {
        T=0, memset(p, -1, sizeof p);
        while(m--)
        {
            scanf("%d %d %d", &st,&en,&flow);
            addEDGE(st,en,flow);
        }
        start=1, end=n;
        printf("%d\n", ISAP(n));
    }
    return 0;
}