Flow Problem

2
3 2
1 2 1
2 3 1
3 3
1 2 1
2 3 1
1 3 1

Case 1: 1
Case 2: 2

题意：题目就是告诉你点和边的数量n和m，然后就是每条边连接的两个点和值，要你求出从1到n的最大流

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

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

//sum是记录最大流量，cur是当前点，flag是标记

    while(true)
    {

//首先找一条最短的从起点到终点的路线切用v记录好流量最小的边
        queue<int> q;	//用一个队列
        memset(vis,0,sizeof(vis));
        memset(f,0,sizeof(f));	//初始化
        q.push(1);
        flag=1;
        v[1]=1<<30;	//起点的最小值初始化无穷大
        while(q.size()&&flag)	//队列没完且没有找到路线
        {
            cur=q.front();	//取当前点
            q.pop();
            for(i=2;i<=n;i++)	//遍历所有点
            if(!vis[i]&&map[cur][i])	//如果没有标记且有这样的路线
            {
                q.push(i);	//入队
                vis[i]=1;	//标记已访问
                f[i]=cur;	//前驱标记
                v[i]=min(map[cur][i],v[cur]);	//最小值在当前边的值和前驱v的值之间取最小的
                if(i==n){flag=0;break;}	//如果找到终点就标记有路线且结束
            }
        }
        if(flag)return sum;	//如果没有路线存在了就结束
        for(i=n;i!=1;i=f[i])	//有路线的话就更新残余网络
        {
            map[f[i]][i]-=v[n];	//正的减最小值
            map[i][f[i]]+=v[n];	//相反的方向就加上来
        }
        sum+=v[n];	//把新流量加上来
    }
}
int main (void)
{
    int i,j,k,l,T,cas=1;
    scanf("%d",&T);
    while(T--&&scanf("%d%d",&n,&m))
    {
        memset(map,0,sizeof(map));
        while(m--&&scanf("%d%d%d",&i,&j,&k))
        map[i][j]+=k;	//这里有重边，只能叠加
        printf("Case %d: %d\n",cas++,EK());
    }
    return 0;
}

HDU--杭电--3549--Flow Problem--最大流

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