他人博客详细讲解:http://www.cnblogs.com/zsboy/archive/2013/01/27/2878810.html
好像大概意思是不停地用bfs找一条增广链,并更新答案,直到找不到为止,构图时需构建反向弧,来让错误的路可以往回走。。
程序:
#include<iostream> #include<cstdio> #include<queue> #include<cmath> #include<vector> #include<cstring> using namespace std; struct ding{ int from,to,cap,now; }; int a[20000],p[20000]; vector<ding>edge; vector<int>g[20000]; int esize=0,n,m; void add(int from1,int to1,int val) { edge.push_back((ding){from1,to1,val,0}); edge.push_back((ding){to1,from1,0,0}); g[from1].push_back(esize); g[to1].push_back(esize+1); esize+=2; } int maxlow(int s,int t) { int ans=0; while (true) { queue<int>q; q.push(s); memset(a,0,sizeof a); a[s]=2100000000; while (!q.empty()) { int k=q.front(); q.pop(); for (int i=0;i<=g[k].size()-1;i++) { ding enow=edge[g[k][i]]; if ((a[enow.to]==0)&&(enow.now<enow.cap)) { a[enow.to]=min(a[k],enow.cap-enow.now); p[enow.to]=g[k][i]; q.push(enow.to); } } if (a[t]) break; } if (!a[t]) break; ans+=a[t]; for (int i=t;i!=s;i=edge[p[i]].from) { edge[p[i]].now+=a[t]; edge[p[i]^1].now-=a[t]; } } return ans; } int main() { int s,t,u,v,w; scanf("%d%d%d%d",&n,&m,&s,&t); for (int i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); add(u,v,w); } printf("%d\n",maxlow(s,t)); return 0; }
原文:http://www.cnblogs.com/2014nhc/p/6602979.html