学步园

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

这个也是简单的最大流问题哦，刚开始还错了二遍  一直搞不懂哪里错了  老是时间超时了  最后发现原来是第一个点没有标记哦

我说呢   数据这么小怎么可然，下次一定要注意了   呵呵 其实跟hdu 1532差不多哦

下面具体代码

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

int bfs()
{
    bool flag[max];
    memset(p,-1,sizeof(p));
    memset(flag,false,sizeof(flag));
    queue<int> que;

    que.push(1);
    flag[1]=true;
    while(!que.empty())
    {
        int e=que.front();

        if(e==n) return true;

        que.pop();
        for(int i=1;i<=n;i++)
        {
            if(map[e][i]&&!flag[i])
            {
                flag[i]=true;

                p[i]=e;
                que.push(i);
            }
        }
    }
    return false;
}

void ek_maxflow()
{
    int u,flow=0;
    while(bfs())
    {
        int min=999999;
        u=n;
        while(p[u]!=-1)
        {
           min=min>map[p[u]][u]?map[p[u]][u]:min;
           u=p[u];
        }
        flow+=min;
        u=n;
        while(p[u]!=-1)
        {
            map[p[u]][u]-=min;
            map[u][p[u]]+=min;
            u=p[u];
        }
    }
    cout<<flow<<endl;
}

int main()
{
    int i,j1,j2,h,t;
    cin>>t;
    for(i=1;i<=t;i++)
    {
        memset(map,0,sizeof(map));
        cin>>n>>m;
        while(m--)
        {
           // cin>>j1>>j2>>h;
            scanf("%d %d %d",&j1,&j2,&h);
            map[j1][j2]+=h;
        }
        cout<<"Case "<<i<<": ";
        ek_maxflow();
    }
    return 0;
}