【POJ】1273 Drainage Ditches 网络最大流

这是一道经典的网络最大流的题目，个人认为这题适合入门小白……

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

说白了就是求点1到点n的网络最大流嘛。。。

附上AC代码：

方法一：EK（Edmonds_Karp）

#include <cstdio>#include <queue>#include <cstring>using namespace std;int n,m,x,y,w,map[210][210];int EK(int s,int e){	int dis[210],PRe[210],ans=0;	queue <int> que;	while (1){		memset(dis,0,sizeof dis);dis[s]=2e9;		memset(pre,0,sizeof pre);		while (!que.empty()) que.pop();		que.push(s);		while (!que.empty()){			int t=que.front();que.pop();			for (int i=1; i<=n; ++i)				if (!dis[i]&&map[t][i]){					dis[i]=min(dis[t],map[t][i]);					pre[i]=t;					que.push(i);				}			if (dis[e]) break;		}		if (!dis[e]) return ans;		ans+=dis[e];		for (int i=e; i!=s; i=pre[i]){			map[pre[i]][i]-=dis[e];			map[i][pre[i]]+=dis[e];		}	}}int main(void){	while (scanf("%d%d",&m,&n)>0){		memset(map,0,sizeof map);		for (int i=1; i<=m; ++i){			scanf("%d%d%d",&x,&y,&w);			map[x][y]+=w,map[y][x]+=0;		}		printf("%d/n",EK(1,n));	}	return 0;}方法二：Dinic
#include <cstdio>#include <queue>#include <cstring>using namespace std;queue <int> que;int n,m,x,y,w,map[210][210],ans,c[210];bool bfs(){	while (!que.empty()) que.pop();	memset(c,0,sizeof c);	que.push(1);c[1]=1;	while (!que.empty()){		int t=que.front();que.pop();		for (int i=1; i<=n; ++i)			if (c[i]==0&&map[t][i]){				c[i]=c[t]+1;				que.push(i);			}	}	if (c[n]) return 1;		else return 0;}int so(int x,int ans){	if (x==n) return ans;	int a;	for (int i=1; i<=n; ++i)		if (c[i]==c[x]+1&&map[x][i]&&(a=so(i,min(ans,map[x][i])))){			map[x][i]-=a;			map[i][x]+=a;			return a;		}	return 0;}int main(void){	while (scanf("%d%d",&m,&n)>0){		memset(map,0,sizeof map);		for (int i=1; i<=m; ++i){			scanf("%d%d%d",&x,&y,&w);			map[x][y]+=w;		}		ans=0;		while (bfs()) ans+=so(1,2e9);		printf("%d/n",ans);	}	return 0;}写在最后：由于这题数据范围过小（n<=200），所以我只是用了邻接矩阵来存边。
对于一些较大的数据，就需要用邻接表或链表来存了。