学步园

Description

Input

Output

Sample Input

5 41 2 401 4 202 4 202 3 303 4 10

Sample Output

50

/*
题目大意：一个农夫为了挖了很多条沟排水。1是pond，m是stream。求最大排水量

题目解答：纯粹的最大流问题.

ps：第一次做脑子糊涂了，居然复制反向边，导致纠结了。这个题目另外要注意的一点是可能产生平行边。

Source Code

Problem: 1273  User: wawadimu 
Memory: 564K  Time: 16MS 
Language: C++  Result: Accepted 

Source Code
*/ 
#include<iostream>
#include<queue>
using namespace std;

#define maxn 220
#define inf INT_MAX
/*struct node
{
	int u,v;
}e[maxn];
*/

int n,m;//边数,顶点数
//int first[maxn],next[maxn];
int flow[maxn][maxn],cap[maxn][maxn];
int a[maxn],pre[maxn];

int maxflow(int s,int t)
{
	int max=0;
	while(1)
	{
		memset(a,0,sizeof(a));
		a[s]=inf;
		queue<int> q;
		q.push(s);
		while(!q.empty())
		{
			int u=q.front();q.pop();
			for(int v=1;v<=m;v++)
			{
				if(!a[v] && cap[u][v] > flow[u][v])
				{
					pre[v]=u;
					a[v]=a[u] > cap[u][v]-flow[u][v] ? cap[u][v]-flow[u][v] : a[u];
					q.push(v);
				}
			}
		}
		if(!a[t]) break;
		for(int x=t;x!=s;x=pre[x])
		{
			flow[pre[x]][x]+=a[t];
			flow[x][pre[x]]-=a[t];
		}
		//cout<<max<<endl;
		max+=a[t];
	}
	return max;
}
int main()
{
	//freopen("1273.txt","r",stdin);
	int s,t;
	int i,j;
	int c,tmp,u,v;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(cap,0,sizeof(cap));
		memset(flow,0,sizeof(flow));
		for(i=1;i<=n;i++)
		{
			scanf("%d%d",&u,&v);
			scanf("%d",&c);
			cap[u][v]+=c;//有多重边
		}
		s=1;t=m;
		int ans=maxflow(s,t);
		printf("%d/n",ans);
	}
	return 0;
}