poj 1273 Drainage Ditches 夜

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<math.h>

using namespace std;
int path[202][202];
bool had[202];
int f[202];
int N,M;
int ans;
int find(int st,int nd)
{
    //cout<<"ttt\n";
    memset(had,false,sizeof(had));
    memset(f,-1,sizeof(had));
    queue<int>str;
    had[st]=true;
    str.push(st);
    int k;
    while(!str.empty())
    {
        k=str.front();
        str.pop();
        for(int i=1;i<=M;i++)
        {
            if(!had[i]&&path[k][i]>0)
            {
                str.push(i);
                //cout<<i<<endl;
                had[i]=true;
                f[i]=k;
                if(i==nd)
                {
                    int minn=20000000;
                    int j=nd;
                    while(j!=st)
                    {
                        minn=min(minn,path[f[j]][j]);
                        j=f[j];
                    }
                    return minn;
                }
            }
        }
    }
    return -1;

}
int main()
{
    int i,j,m;
    while(cin>>N>>M)
    {
        ans=0;
        memset(path,0,sizeof(path));
        while(N--)
        {
            cin>>i>>j;
            cin>>m;
            path[i][j]+=m;
        }
        int k;
        while((k=find(1,M))!=-1)
        {
            int i=M;
            ans+=k;
            while(i!=1)
            {
                path[f[i]][i]-=k;
                path[i][f[i]]+=k;
                i=f[i];
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}