学步园

题目 http://acm.hdu.edu.cn/showproblem.php?pid=1532

这是最大流的一个简单题哦   我是用Edmond-Karp来做的哦   思想是每次找出一条最短路，然后在这条最短路里找出一条边最小的权值哦，

这条路上的边全都都减去最小权值，也是更新哦。重复上述过程，直到没有最短路径出现哦。。。

具体看代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
#define max 201
int map[max][max];
int p[max];
int n,m;

bool ek_bfs()  //不断寻找最短路哦
{
    queue<int> que;
    bool flag[max];
    memset(flag,false,sizeof(flag));  //标记哦
    memset(p,-1,sizeof(p));    //记录
    que.push(1);
    flag[1]=true;

    while(!que.empty())
    {
        int e=que.front();

        if(e==m) return true;

        que.pop();
        for(int i=1;i<=m;i++)
        {
            if(map[e][i]&&!flag[i])
            {
                flag[i]=true;
                p[i]=e;
                que.push(i);  //入队
            }
        }
    }

    return false;
}


void ek_max_flow()
{
    int u,flow_ans=0,mn;

    while(ek_bfs())
    {
        mn=9999999;
        u=m;

        while(p[u]!=-1)  //找出最小的那条路哦
        {
            mn=mn>map[p[u]][u]?map[p[u]][u]:mn;
            u=p[u];
        }

        flow_ans+=mn;

        u=m;
        while(p[u]!=-1)  //更新哦
        {
            map[p[u]][u]-=mn;
            map[u][p[u]]+=mn;
            u=p[u];
        }
    }
    cout<<flow_ans<<endl;

}

int main()
{
    int i,j,t;
    while(cin>>n>>m)
    {
        memset(map,0,sizeof(map));
        while(n--)
        {
            cin>>i>>j>>t;
            map[i][j]+=t;
        }
        ek_max_flow();
    }
    return 0;
}