「转载」最大流
/* 题目：poj 1273 Drainage Ditches (网络流最大流) 题意： 有n道水渠,和m个节点,其中每道水渠都有一个最大流 问从1节点到m节点的最大流 Sample Input 5 4 1 2 40 1 4 20 2 4 20 2 3 30 3 4 10 Sample Output 50 解题： 最大流 利用 edmonds_karp算法 bfs */#include<stdio.h> #include<string.h> #define M 230 #define INF 0x7FFFFFFF #define min(a,b) a<b?(a):(b) /* f[i]存储第i点存储的水 residual[i][j]存储从i到j水渠的剩余流量 pre存储前驱节点*/ int residual[M][M],pre[M],f[M],q[M]; int n,m; void input() { int x,y,z; memset(residual,0,sizeof(residual)); for(int i=0;i<n;i++) { scanf("%d%d%d",&x,&y,&z); residual[x][y]+=z;/* 因为存在回路 */ } } int bfs() { for(int i=1;i<=m;i++) f[i]=INF; q[0]=1; memset(pre,-1,sizeof(pre)); int head=-1,tail=0,cur; while(head<tail) { ++head; cur=q[head]; if(cur==m) return f[m]; for(int i=1;i<=m;i++) { /*如果该点已经走过或者从cur到i的水渠的流量为0时*/ if(pre[i]!=-1||residual[cur][i]==0) continue; pre[i]=cur; f[i]=min(f[cur],residual[cur][i]); ++tail; q[tail]=i; } } return -1; } int EK() { int ans=0; while(1) { int tmp=bfs(); if(tmp==-1) return ans; ans+=tmp; int a=m; int b; while(a!=1) { b=pre[a]; residual[b][a]-=tmp;/* 正向流减小 */ residual[a][b]+=tmp;/* 反向流增加 */ a=b; } } } int main() { while(scanf("%d%d",&n,&m)==2) { input(); printf("%d\n",EK()); } return 0; }