【POJ1273】Drainage Ditches-最大流问题

测试地址：Drainage Ditches

题目大意：一个排水系统形成一个网络，有N条排水沟，M个交叉点（编号为1~M），每条水沟都把水从一个交叉点Si单向送到另一个交叉点Ti，每条水沟都有一个排水效率Ci，意思是单位时间内最多可以排水的量，现在有很多积水在交叉点1，求把积水排到交叉点M时该排水系统最大的排水效率。

做法：典型的网络流中的最大流问题，网上教程很多，这里不再赘述，本人用的是Dinic算法，当然用其他方法做也可以。

以下是本人代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#define inf 999999999
using namespace std;
int n,m,first[210],ans;
int lay[210]; //点的层数
struct {int v,c,next;} e[410]; //存储边的结构：邻接表

bool bfs(int s) //BFS顶点分层
{
  bool vis[210]={0};
  queue<int> q;
  q.push(s);
  lay[s]=0;vis[s]=1;lay[n]=-1;
  while(!q.empty())
  {
    int v=q.front();q.pop();
    for(int i=first[v];i;i=e[i].next)
	  if (e[i].c!=0&&!vis[e[i].v])
	  {
	    lay[e[i].v]=lay[v]+1;
		vis[e[i].v]=1;
		q.push(e[i].v);
	  }
  }
  if (lay[n]==-1) return 0;
  else return 1;
}

int dfs(int v,int maxf,int t)
{
  if (v==t) return maxf;
  int ret=0,f;
  for(int i=first[v];i;i=e[i].next)
    if (e[i].c&&lay[e[i].v]==lay[v]+1)
	{
	  f=dfs(e[i].v,min(maxf-ret,e[i].c),t);
	  e[i].c-=f;
	  e[i^1].c+=f;
	  ret+=f;
	  if (ret==maxf) return ret;
	}
  return ret;
}

int Dinic(int s,int t)
{
  int ans=0;
  while (bfs(s)) ans+=dfs(s,inf,t);
  return ans;
}

int main()
{
  while(scanf("%d%d",&m,&n)!=EOF)
  {
    memset(first,0,sizeof(first));
	for(int i=1,a,b,c;i<=m;i++)
	{
	  scanf("%d%d%d",&a,&b,&c);
	  e[2*i-1].v=b;e[2*i-1].c=c;e[2*i-1].next=first[a];first[a]=2*i-1; //构造真边
	  e[2*i].v=a;e[2*i].c=0;e[2*i].next=first[b];first[b]=2*i; //构造回退边
	}
	printf("%d
",Dinic(1,n));
  }
  
  return 0;
}