usaco_4_2_1_ditch_网络流.cpp

usaco自己做的1到5章的代码

/*
ID:wangyuc2
PROG:ditch
LANG:C++
*/
#include <iostream>
#include <fstream>
#include <memory.h>
#include <cmath>
#include <algorithm>
#include <queue>
#define inf 1000000000
#define cin fin
using namespace std;
ifstream fin("ditch.in");
ofstream fout("ditch.out");
//Ford-Fulkerson 
#define MAX 220 

using namespace std; 

int a[MAX][MAX];     
int pre[MAX];
int flow;            //最大流 
int n,m;               //节点数
int s,t;             //源点,汇点 

int findpath() 
{
    int queue[MAX]={0};
    int mark[MAX]={0};
    int head=0,tail=1;
    queue[tail]=s;
    mark[s]=1; 
    while(head!=tail)
    {
        head++;
        for(int i=0;i<n;i++)    //节点从0算起 
            if(i != queue[head] && mark[i]==0 && a[queue[head]][i]>0)
            {
                queue[++tail]=i;
                mark[i]=1;
                pre[i]=queue[head];
                if(i==t)return 1;
            }
    }
    return 0;
} 

int ford()
{
	int i;
    if(findpath()==0)
        return 0;
    int min=a[pre[t]][t];
    for(i=t;i!=s;i=pre[i])
    {
        if(a[pre[i]][i]<min)
            min=a[pre[i]][i];
    }
    for(i=t;i!=s;i=pre[i])
    {
        a[pre[i]][i]-=min;
        a[i][pre[i]]+=min;
    }
    flow+=min;
    return 1; 
}            

int main()
{
    int i,j,k,x,y;
    for(i=0;i<=n;i++)
        for(j=0;j<=n;j++)
            a[i][j]=0; 
    flow=0;
    cin>>m>>n;
    for(i=0;i<m;i++)
    {
        cin>>x>>y>>k;
        x--;
        y--;
		a[x][y]+=k;
    }
    s=0;
    t=n-1;
    while(ford()); 
    fout<<flow<<endl;
   // system("PAUSE");
    return 0;
}