HDU 1532 && POJ 1273 Drainage Ditches （网络流）
转载请注明出处：http://blog.csdn.net/a1dark
分析：刚学会了EK算法、然后重新找了一题来做、写起来非常流畅、连编译运行都没有、直接一次AC、爽死了、弱弱的我貌似有网络流天赋？嘿嘿、继续加油！
#include<stdio.h>#include<queue>#include<iostream>using namespace std;#include<string.h>#define MAXN 205#define INF 0xfffffffint map[MAXN][MAXN];int pre[MAXN];int vis[MAXN];int m,n;int bfs(int s,int t){ memset(pre,-1,sizeof(pre)); memset(vis,0,sizeof(vis)); queue<int > q; q.push(s); vis[s]=1; pre[s]=s; while(!q.empty()){ int now=q.front(); q.pop(); for(int i=1;i<=n;i++){ if(map[now][i]&&!vis[i]){ pre[i]=now; vis[i]=1; if(i==t)return 1; q.push(i); } } } return 0;}int EK(int s,int t){ int i,d,flow=0; while(bfs(s,t)){ d=INF; for(i=t;i!=s;i=pre[i]) if(d>=map[pre[i]][i]) d=map[pre[i]][i]; for(i=t;i!=s;i=pre[i]){ map[pre[i]][i]-=d; map[i][pre[i]]+=d; } flow+=d; } return flow;}int main(){ while(scanf("%d%d",&m,&n)!=EOF){ memset(map,0,sizeof(map)); int s,e,v; for(int i=1;i<=m;i++){ scanf("%d%d%d",&s,&e,&v); map[s][e]+=v; } printf("%d\n",EK(1,n)); } return 0;}