Drainage Ditches

5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10

50

题意：就是一个池塘里面的水流到小溪吧（其实我也不懂），告诉你沟与沟之间的过道数n和沟的数目m，然后告诉你每条过道的信息，要你求出从1到m的最大流

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define Max 222
using namespace std;
int n,m,vis[Max],f[Max],v[Max],map[Max][Max];

//vis是标记数组，f是前驱，v是最小值，map是地图
int EK()
{
    int i,j,k,l,cur,sum=0,mm,flag;

//cur是当前沟的号码，sum是最大流的值，flag是标记
    while(true)
    {
        queue<int> q;	//定义一个队列
        memset(vis,0,sizeof(vis));
        memset(f,0,sizeof(f));	//初始化
        v[1]=1<<30;	//起点的最小值初始化为无穷大
        q.push(1);
        flag=1;
        while(q.size()&&flag)	//队列不为空且标记未找到路线
        {
            cur=q.front();	//取当前点
            q.pop();
            for(i=2;i<=m;i++)	//遍历所有点
            if(!vis[i]&&map[cur][i])	//标记未访问且有此路线
            {
                q.push(i);	//入队
                vis[i]=1;	//标记已访问
                f[i]=cur;	//记录前驱
                v[i]=min(map[cur][i],v[cur]);	//最小值取当前路线与前驱之间的最小值
                if(i==m){flag=0;break;}	//如果找到终点就标记且结束
            }
        }
        if(flag)return sum;	//没找到路线就结束
        for(i=m;i!=1;i=f[i])	//找到路线就更新残余网络
        {
            map[f[i]][i]-=v[m];	//正方向的减去最小值
            map[i][f[i]]+=v[m];	//反方向的加上最小值
        }
        sum+=v[m];	//加上当前流
    }
}
int main (void)
{
    int i,j,k,l;
    while(~scanf("%d%d",&n,&m))
    {
        memset(map,0,sizeof(map));
        while(n--&&scanf("%d%d%d",&j,&k,&l))
        map[j][k]+=l;
        printf("%d\n",EK());
    }
    return 0;
}

HDU--杭电--1532--Drainage Ditches--最大流

原文：http://blog.csdn.net/jingdianitnan/article/details/18901543