学步园

ditch

描述

在农夫约翰的农场上，每逢下雨，贝茜最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名一流的技师，农夫约翰已经在每条排水沟的一端安上了控制器，这样他可以控制流入排水沟的水流量。

农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。

根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。

格式

PROGRAM NAME:ditch

INPUT FORMAT:

(file ditch.in)

第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 FORMAT:

(file ditch.out)

输出一个整数，即排水的最大流量。

SAMPLE INPUT

5 4

1 2 40

1 4 20

2 4 20

2 3 30

3 4 10

SAMPLE OUTPUT

50

评测链接：http://poj.org/problem?id=1273

解法：sap。

            d[]记录每个点所属层次，vd[]记录每一层有多少个点，g[][]记录边。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 200+10
using namespace std;

int m,n;
int d[maxn],vd[maxn],g[maxn][maxn];

void init()
{
  freopen("ditch.in","r",stdin);
  freopen("ditch.out","w",stdout);
}

void readdata()
{
  memset(g,0,sizeof(g));
  memset(d,0,sizeof(d));
  memset(vd,0,sizeof(vd));
  vd[0]=m;

  int i,s,e,c;
  for(i=1;i<=n;i++)
    scanf("%d%d%d",&s,&e,&c),g[s][e]+=c;
}

int sap(int u,int flow)
{
  if(u==m)return flow;
  
  int i,t,res=flow;
  for(i=1;i<=m;i++)
    if(g[u][i]>0 && d[u]==d[i]+1)
      {
        t=sap(i,min(g[u][i],res));
        g[u][i]-=t,g[i][u]+=t;
        if(!(res-=t))return flow;
      }
  if(d[0]<m+1)//断层判断
    {
      if(!(--vd[d[u]]))d[0]=m+1;
      ++vd[++d[u]];
    }    
  return flow-res;  
}

void work()
{
  int ans=0;
  for(;d[0]<m+1;)
    ans+=sap(1,1000000000);
  printf("%d\n",ans);  
}

int main()
{
  init();
  while(scanf("%d%d",&n,&m)!=EOF)
    readdata(),work();  
  return 0;
}