【POJ - 1273】Drainage Ditches（网络流，最大流，模板）

题干：

现在有m个池塘(从1到m开始编号,1为源点,m为汇点),及n条水渠,给出这n条水渠所连接的点和所能流过的最大流量，求从源点到汇点能流过的最大流量。

Input

输入包括几种情况。 对于每种情况，第一行包含两个空格分隔的整数，N（0 <= N <= 200）和M（2 <= M <= 200）。 N是Farmer John挖的沟渠数量。 M是那些沟渠的交叉点。 以下N行中的每一行包含三个整数，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 10

Sample Output

50

解题报告：

   这是一道KK，EK，dinic都可以0ms跑过的板子题。。

AC代码：

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int tot;
struct Edge {
	int to,ne,v;
} e[100005 * 2];
int head[10005];
int st,ed;
int dis[10050],q[10005];//一共多少个点跑bfs，dis数组和q数组就开多大。 
void insert(int u,int v,int w) {
	e[++tot].to=v;
	e[tot].v=w;
	e[tot].ne=head[u];
	head[u]=tot;
}
bool bfs(int st,int ed) {
	memset(dis,-1,sizeof(dis));
	int front=0,tail=0;
	q[tail++]=st;
	dis[st]=0;
	while(front<tail) {
		int cur = q[front];
		front++;
		for(int i = head[cur]; i!=-1; i = e[i].ne) {
			if(e[i].v&&dis[e[i].to]<0) {
				q[tail++]=e[i].to;
				dis[e[i].to]=dis[cur]+1;
			}
		}
	}
	if(dis[ed]==-1) return 0;
	return 1;
}
int dfs(int cur,int f) {
	if(cur==ed) return f;
	int w,flow=0;
	for(int i = head[cur]; i!=-1; i = e[i].ne) {		
		if(e[i].v&&dis[e[i].to]==dis[cur]+1) {
			w=f-flow;
			w=dfs(e[i].to,min(w,e[i].v));
			e[i].v-=w;
			e[i+1].v+=w;
			flow+=w;
			if(flow==f) return f;
		}		
	}
	if(!flow)dis[cur]=-1;
	return flow;
}
int dinic() {
	int ans = 0;
	while(bfs(st,ed)) ans+=dfs(st,0x7fffffff);
	return ans;
}
int main() {

	while(~scanf("%d%d",&m,&n)) {
		tot=2;
		st=1,ed=n;
		for(int i = 1; i<=n; i++) head[i] = -1;
		for(int a,b,c,i = 1; i<=m; i++) {
			scanf("%d%d%d",&a,&b,&c);
			insert(a,b,c);
			insert(b,a,0);
		}		
		printf("%d\n",dinic());				
	}

	return 0;
}