這是一道經典的網絡最大流的題目，個人認為這題適合入門小白……

題目大意：現在有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），所以我只是用了鄰接矩陣來存邊。
對于一些較大的數據，就需要用鄰接表或鏈表來存了。