Description
在农夫约翰的农场上,每逢下雨,贝茜最喜欢的三叶草地就积聚了一潭水.这意味着草地被水淹没了,并且小草要继续生长还要花相当长一段时间.因此,农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心,雨水会流向附近的一条小溪）.作为一名一流的技师,农夫约翰
已经在每条排水沟的一端安上了控制器,这样他可以控制流入排水沟的水流量.
农夫约翰知道每一条排水沟每分钟可以流过的水量,和排水系统的准确布局（起点为水潭而终点为小溪的一张网）.需要注意的是,有些时候从一处到另一处不只有一条排水沟.
根据这些信息,计算从水潭排水到小溪的最大流量.对于给出的每条排水沟,雨水只能沿着一个方向流动,注意可能会出现雨水环形流动的情形.
Input
第1 行: 两个用空格分开的整数N (0 <= N <= 200) 和 M (2 <= M <= 200).N 是农夫约翰已经挖好的排水沟的数量,M 是排水沟交叉点的数量.交点1 是水潭,交点M 是小溪.
第二行到第N+1 行: 每行有三个整数,Si, Ei, 和 Ci.Si 和 Ei (1 <= Si, Ei <= M) 指明排水沟两端的交点,雨水从Si 流向Ei.Ci (0 <= Ci <= 10,000,000)是这条排水沟的最大容量.
Output
输出一个整数,即排水的最大流量.
Sample Input
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10Sample Output
50
题目分析：
最大流模板题 连重建图都不用
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int tot=1,head[2333],to[2333],val[2333],net[2333];
void add(int x,int y,int z)
{
net[++tot]=head[x],to[tot]=y,val[tot]=z,head[x]=tot;
net[++tot]=head[y],to[tot]=x,val[tot]=0,head[y]=tot;
}
int ans;
int dis[2333];
int bfs()
{
queue<int>q;
memset(dis,0,sizeof dis);
q.push(1);
dis[1]=1;
while(q.size())
{
int nmp=q.front();
q.pop();
for(int i=head[nmp];i;i=net[i])
if(val[i]>0&&!dis[to[i]])
{
dis[to[i]]=dis[nmp]+1;
q.push(to[i]);
if(to[i]==n) return 1;
}
}
return 0;
}
int dinic(int x,int flow)
{
int tmp,temp=flow;
if(x==n) return flow;
for(int i=head[x];i;i=net[i])
if(val[i]>0&&dis[to[i]]==dis[x]+1)
{
tmp=dinic(to[i],min(val[i],temp));
if(tmp==0) dis[to[i]]=0;
temp-=tmp,val[i]-=tmp,val[i^1]+=tmp;
if(!temp) break;
}
return flow-temp;
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
add(x,y,c);
}
while(bfs()) ans+=dinic(1,1<30);
printf("%d",ans);
return 0;
}
