学步园

http://acm.pku.edu.cn/JudgeOnline/problem?id=1273

自己的第一个最大流程序，作个纪念。

#include <iostream>
#include <string.h>
using namespace std;
const int max_size = 210;
long c[max_size][max_size];//容量
long flow[max_size][max_size];//初始化任意两点间的流量位0
int que[max_size];
int front=0,rear=0;
int pre[max_size];//每个节点在增广路径上的前驱
int d[max_size];
void edmonds_karp(int n,int s,int t)
{
    int i = 0;
    while(true)   
    {
            //每次寻找增广路径都要初始化相关数组和变量
            memset(que,0,sizeof(que));   
            memset(pre,-1,sizeof(pre));
            d[s]=0x3f3f3f3f;//开始设置可扩容量为0xffff
            front=rear=0;
            que[rear++]=s;
            while(front<rear && pre[t]<0)
            {
                    int p = que[front];
                    front++;
                    for(i=1;i<=n;i++)
                    {
                            if(pre[i]<0 && (c[p][i]-flow[p][i]))
                            //if(c[p][i]>0&& pre[i]==-1 && (c[p][i]-flow[p][i]))
                            {
                                pre[i]=p;
                                que[rear++]=i;
                                int tmp = c[p][i]-flow[p][i];
                                if(d[p]>tmp)//寻找增光路经path上的最小值作为更新值,d[i]表示通过BFS寻找增广路径到节点i为止时的最小“可扩容量”
                                        d[i]=tmp;
                                else
                                        d[i]=d[p];
                            }
                    }
            }
            if(pre[t]<0)//已经没有增光路经可找了
                    break;
            //更新flow数组，添加可扩容量
            for(i=t;i!=s;i=pre[i])//i==s是结束件
，这里开始用pre[i]!=-1作为结束条件，结果TLE无数次，估计造成了死循环

            {
                //d[t]表示最后找到增光路经后,到t为止路径上的最小“可扩容量”
                //cout<<i<<" ";
                flow[pre[i]][i]+=d[t];//正向增加流量：pre[i]->i
                flow[i][pre[i]]-=d[t];//反向增加流量: i->pre[i]
            }
    }
}
int main()
{
        int i =0;
        int j = 0;
        int cost = 0;
        int n = 0;
        int m = 0;
        int x,y;
        while(scanf("%d %d",&n,&m)!=EOF)
        {
                memset(c,0,sizeof(c));
                memset(flow,0,sizeof(flow));
                for(i=0;i<n;i++)
                {
                    scanf("%d %d %d",&x,&y,&cost);
                    c[x][y]+= cost;
                }
                edmonds_karp(m,1,m);
                long max_flow=0;
                for(i=2;i<=m;i++)
                        max_flow+=flow[1][i];
                cout<<max_flow<<endl;
        }
}