学步园

刚学最大流算法，一道简单的最大流问题，思路就是找出每条从s->t的路径中最小的残量a[t]（最大流量-已流的流量）将路径上的流量都增加a[t]，直到残量为0；

#include<iostream>
#include<stdio.h>
#include<queue>
#include<string.h>
#define INF 99999999
using namespace std;
int m,n,map[250][250],a[250],flow[250][250],p[250];
int EK(int s,int t)
{
    int sum=0;
    queue<int>q;
    memset(flow,0,sizeof(flow));
    for(;;)
    {
        memset(a,0,sizeof(a));//记录残量
        a[s]=INF;
        q.push(s);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            for(int i=2;i<=n;i++)
            if(a[i]==0&&map[u][i]>flow[u][i])
            {
                p[i]=u;q.push(i);
                a[i]=a[u]<map[u][i]-flow[u][i]?a[u]:map[u][i]-flow[u][i];
            }
        }//找出s->t路径的最小残量
            if(a[t]==0)break;//最小残量为0;s->t之间流量达到最大
            for(int i=t;i!=s;i=p[i])//s->t路径上的流量都加上最小残量a[t];
            {
                flow[p[i]][i]+=a[t];
                flow[i][p[i]]-=a[t];
            }
            sum+=a[t];//记录流量
    }
    return sum;
}

int main()
{
    int i,j,c,b,x;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        memset(map,0,sizeof(map));
        memset(p,0,sizeof(p));
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&c,&b,&x);
            map[c][b]+=x;//变态，还要考虑重边
        }
        j=EK(1,n);
        printf("%d\n",j);
    }
    return 0;
}