POJ 1273最初のSAP(ISAP)

/*sapは长い间学んで、ずっと手书きをする勇気がなくて、结果は书かないで永远に本当の理解のアルゴリズムの意味ができなくて、sap理论の多くのアルゴリズムの本の上ですべて说明があって、しかし私はやはり数学の専门の図论の本を読むことを提案して、例えば《図の理论があって、アルゴリズムと応用があります》、この本の内容はとてもすばらしくて、読んだことがあることを信じてすべて知っています他のアルゴリズムの本よりずっと透き通っている.SAPの最適化は、チェーンが切れたときに直接終了することができ、また、現在のアークの最適化があります.この2つの最適化は一言+1つの配列で解決され、かなりお得で、良いISAPの実行効率は本当に高く、私が書いたISAPはチェーン式の前方星法で表されています.これはテンプレートにしておきましょう.あまり上手ではありませんが..*/
 

#include<iostream>

#include<cstdio>

#include<memory.h>

#include<cmath>

using namespace std;



#define MAXN 500

#define MAXE 40000

#define INF 0x7fffffff



long ne,nv,tmp,s,t,index;



struct Edge{

    long next,pair;

    long v,cap,flow;

}edge[MAXE];

long net[MAXN];

long ISAP()

{

    long numb[MAXN],dist[MAXN],curedge[MAXN],pre[MAXN];

    long cur_flow,max_flow,u,tmp,neck,i;

    memset(dist,0,sizeof(dist));

    memset(numb,0,sizeof(numb));

    memset(pre,-1,sizeof(pre));

    for(i = 1 ; i <= nv ; ++i)

        curedge[i] = net[i];

    numb[nv] = nv;

    max_flow = 0;

    u = s;

    while(dist[s] < nv)

    {

        /* first , check if has augmemt flow */

        if(u == t)

        {

            cur_flow = INF;

            for(i = s; i != t;i = edge[curedge[i]].v) 

            {  

                if(cur_flow > edge[curedge[i]].cap)

                {

                    neck = i;

                    cur_flow = edge[curedge[i]].cap;

                }

            }

            for(i = s; i != t; i = edge[curedge[i]].v)

            {

                tmp = curedge[i];

                edge[tmp].cap -= cur_flow;

                edge[tmp].flow += cur_flow;

                tmp = edge[tmp].pair;

                edge[tmp].cap += cur_flow;

                edge[tmp].flow -= cur_flow;

            }

            max_flow += cur_flow;

            u = neck;

        }

        /* if .... else ... */

        for(i = curedge[u]; i != -1; i = edge[i].next)

            if(edge[i].cap > 0 && dist[u] == dist[edge[i].v]+1)

                break;

        if(i != -1)

        {

            curedge[u] = i;

            pre[edge[i].v] = u;

            u = edge[i].v;

        }else{

            if(0 == --numb[dist[u]]) break;

            curedge[u] = net[u];

            for(tmp = nv,i = net[u]; i != -1; i = edge[i].next)

                if(edge[i].cap > 0)

                    tmp = tmp<dist[edge[i].v]?tmp:dist[edge[i].v];

            dist[u] = tmp + 1;

            ++numb[dist[u]];

            if(u != s) u = pre[u];

        }

    }

    

    return max_flow;

}

int main() {

    long i,j,np,nc,m,n;

    long a,b,val;

    long g[MAXN][MAXN];

    while(scanf("%d%d",&ne,&nv)!=EOF)

    {

        s = 1;

        t = nv;

        memset(g,0,sizeof(g));

        memset(net,-1,sizeof(net));

        for(i=0;i<ne;++i)

        {

            scanf("%ld%ld%ld",&a,&b,&val);

            g[a][b] += val;

         }

         for(i=1;i<=nv;++i)

             for(j = i; j <= nv;++j)

                 if(g[i][j]||g[j][i])

                 {

                     edge[index].next = net[i];

                     edge[index].v = j;

                     edge[index].cap = g[i][j];

                     edge[index].flow = 0;

                     edge[index].pair = index+1;

                     net[i] = index++;

                     edge[index].next = net[j];

                     edge[index].v = i;

                     edge[index].cap = g[j][i];

                     edge[index].flow = 0;

                     edge[index].pair = index-1;

                     net[j] = index++;

                 }

        printf("%ld
",ISAP());

    }

    return 0;

}