pe maxFlow(int sNode,int eNode,int n){//源点与汇点 captype minh,ans=0; queue
q; memset(h,0,sizeof(h)); memset(vf,0,sizeof(vf)); h[sNode]=n+1; //源点的高度 vf[sNode]=MAX; //源点的余流 q.push(sNode); while(!q.empty()){ int u=q.front(); q.pop(); minh=MAX; for(int i=head[u]; i!=-1; i=edg[i].nxt){ int v=edg[i].to; captype fp; if(edg[i].c
0 ){ minh=min(minh, h[v]); if(u==sNode || h[u]==h[v]+1){ edg[i].c-=fp; edg[i^1].c+=fp; //反向边，给个反回的通道 vf[u]-=fp; vf[v]+=fp; if(v==eNode) ans+=fp; //当到达汇点时，就加入最大流中 if(v!=sNode && v!=eNode ) //只有即不是源点，也不是汇点时才能进队列 q.push(v); } } if(vf[u]==0) break; //如果顶点的余流为0，则可以跳出for循环 } //如果不是源点（也非汇点），且顶点仍有余流，则重新标记 高度+1 入队 //这里赋值为最低的相邻顶点的高度高一个单位,也可以简单的在原高度+1 if(u!=sNode && vf[u]>0){ h[u] = minh + 1; q.push(u); } } return ans; } int main(){ int n,m,u,v; captype c; while(scanf("%d%d",&m,&n)>0){ init(); while(m--){ scanf("%d%d%I64d",&u,&v,&c); addEdg(u,v,c); } printf("%I64d\n",maxFlow(1,n,n)); } }
方法三：EK
#include
#include
#include
using namespace std; #define captype __int64 const int N = 205; captype cap[N][N],f[N][N],rest[N]; int sNode,eNode,pre[N]; void init(){ memset(f,0,sizeof(f)); memset(cap,0,sizeof(cap)); } bool searchPath(int n){//找一条增广路 bool vist[N]={0}; queue
q; int u,v; u=sNode; vist[u]=1; pre[u]=u; rest[u]=1<<30; q.push(u); while(!q.empty()){ u=q.front(); q.pop(); for(v=1; v<=n; v++) if(!vist[v]&&cap[u][v]-f[u][v]>0) { vist[v]=1; pre[v]=u; if(cap[u][v]-f[u][v]>rest[u]) rest[v]=rest[u]; else rest[v]=cap[u][v]-f[u][v]; if(v==eNode) return true; q.push(v); } } return false; } captype maxflow(int s,int t,int n){ captype ans=0; sNode=s; eNode=t; while(searchPath(n)){ ans+=rest[eNode]; int v=eNode; while(v!=sNode){ int u=pre[v]; f[u][v]+=rest[eNode]; f[v][u]-=rest[eNode];//给一个回流的机会 v=u; } } return ans; } int main(){ int n,m,u,v; captype c; while(scanf("%d%d",&m,&n)>0){ init(); while(m--){ scanf("%d%d%I64d",&u,&v,&c); cap[u][v]+=c; } printf("%I64d\n",maxflow(1,n,n)); } }
?
?