模板题：POJ1273

EK:

#include <queue>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int n,m,jy,map[305][305],c[305][305],a[305],p[305];

bool vis[305];

int M(int e)

{

    int f=0;

    queue<int>q;

    while(1){

        memset(a,0,sizeof(a));

        memset(vis,0,sizeof(vis));

        a[1]=0x3fffffff;vis[1]=1;q.push(1);

        while(!q.empty()){

            jy=q.front();q.pop();

            for(int i=1;i<=e;i++){

                if(!vis[i]&&map[jy][i]-c[jy][i]>0)

                {

                    vis[i]=1;

                    a[i]=min(a[jy],map[jy][i]-c[jy][i]);

                    p[i]=jy;

                    q.push(i);

                }

            }

        }

        if(a[e]==0)break;

        for(int i=e;i!=1;i=p[i]){

            c[i][p[i]]-=a[e];

            c[p[i]][i]+=a[e];

        }

        f+=a[e];

    }

    return f;

}

int main()

{

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        memset(map,0,sizeof(map));

        memset(c,0,sizeof(c));

        memset(p,0,sizeof(p));

        for(int i=1;i<=n;i++)

        {

            register int xx,yy,ee;

            scanf("%d%d%d",&xx,&yy,&ee);

            map[xx][yy]+=ee;

        }

        printf("%d\n",M(m));

    }

}

Dinic：

#include <queue>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define N 444

int tot,next[N],first[N],w[N],v[N],n,m,ch[N];

void add(int from,int to,int weight){

    v[tot]=to;w[tot]=weight;

    next[tot]=first[from];

    first[from]=tot++;

}

bool tell(){

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

    queue<int> q;

    q.push(1);ch[1]=0;

    while(!q.empty()){

        int t=q.front();q.pop();

        for(int i=first[t];~i;i=next[i])

            if(w[i]&&ch[v[i]]==-1)

                q.push(v[i]),ch[v[i]]=ch[t]+1;

    }

    return ch[n]!=-1;

}

int zeng(int a,int b){

    if(a==n)return b;

    int r=0;

    for(int i=first[a];~i&&b>=r;i=next[i])

        if(ch[a]+1==ch[v[i]]&&w[i]){

            int t=zeng(v[i],min(b-r,w[i]));

            w[i]-=t;w[i^1]+=t;r+=t;

        }

    if(!r)ch[a]=-1;

    return r;

}

int dinic(){

    int ans=0,jy;

    while(tell())while(jy=zeng(1,0x3fffffff))ans+=jy;

    return ans;

}

int main()

{

    while(scanf("%d%d",&m,&n)!=EOF){

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

        register int xx,yy,zz;

        tot=0;

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

            scanf("%d%d%d",&xx,&yy,&zz);

            add(xx,yy,zz);add(yy,xx,0);

        }

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

    }

}