Ford-Fulkerson 标号法求网络最大流

使用Ford-Fulkerson 标号法求网络最大流。

①c、f初始化为INF表示该边不存在

#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <queue> #include <iomanip> #include <algorithm> #define maxn 10010 #define INF 0xfffffff using namespace std; struct ArcType { int c,f;//容量、流量 }; ArcType edge[maxn][maxn]; int n,m;//顶点数、弧数 int flag[maxn];//顶点状态：-1——未标号；0——已标号未检查；1——已标号已检查 int prev[maxn];//标号的第一个分量：指明标号从哪个顶点而来，以便找出可改进量 int alpha[maxn];//标号的第二个分量：可改进量α int que[maxn];//相当于BFS中的队列 int v;//队列头元素 int qs,qe;//队首队尾的位置 int i,j; void ford()//标号法求网络最大流 { while(1)//标号，直到不存在可改进路 { memset(flag,-1,sizeof(flag)); memset(prev,-1,sizeof(prev)); memset(alpha,-1,sizeof(alpha)); flag[0]=0; prev[0]=0; alpha[0]=INF; qs=qe=0; que[qe]=0;//源点0入队列 ++qe; while(qs<qe&&flag[n-1]==-1) { v=que[qs];//取队首元素 ++qs; for(i=0; i<n; ++i)//检查顶点v的正向和反向邻接点 if(flag[i]==-1) { if(edge[v][i].c<INF&&edge[v][i].f<edge[v][i].c)//正向且未满 { flag[i]=0;//给顶点i标号，但此时未检查 prev[i]=v; alpha[i]=min(alpha[v],edge[v][i].c-edge[v][i].f); que[qe]=i;//顶点i入队 ++qe; } else if(edge[i][v].c<INF&&edge[i][v].f>0)//反向且有流量 { flag[i]=0; prev[i]=-v; alpha[i]=min(alpha[v],edge[i][v].f); que[qe]=i; ++qe; } } flag[v]=1;//标记顶点i已经检查 } if(flag[n-1]==-1||alpha[n-1]==0) break;//汇点无标号或汇点的调整量为0 int k1=n-1,k2=abs(prev[k1]); int a=alpha[n-1];//可改进量α while(1) { if(edge[k2][k1].f<INF) edge[k2][k1].f+=a;//正向 else edge[k1][k2].f-=a;//反向 if(k2==0) break;//一直调整到源点0 k1=k2; k2=abs(prev[k2]); } } int maxflow=0;//最大流量 for(i=0; i<n; ++i) for(j=0; j<n; ++j) { if(i==0&&edge[i][j].f<INF) maxflow+=edge[i][j].f; if(edge[i][j].f<INF) cout<<i<<"->"<<j<<":"<<edge[i][j].f<<endl; } cout<<"maxflow:"<<maxflow<<endl; } int main() { int u,v,c,f;//弧的起点终点容量流量 cin>>n>>m;//顶点个数、弧数 for(i=0; i<n; ++i) for(j=0; j<n; ++j) edge[i][j].c=edge[i][j].f=INF;//初始化，INF表示无边相连 for(i=0; i<m; ++i) { cin>>u>>v>>c>>f; edge[u][v].c=c;//构造邻接矩阵 edge[u][v].f=f; } ford(); return 0; } /* 6 10 0 1 8 2 0 2 4 3 1 3 2 2 1 4 2 2 2 1 4 2 2 3 1 1 2 4 4 0 3 4 6 0 3 5 9 3 4 5 7 2 */

②未初始化

void ford()//标号法求网络最大流 { int flow[maxn][maxn];//节点之间的流量Fij int prev[maxn];//可改进路径上前一个节点的标号，相当于标号的第一个分量 int minflow[maxn];//每个顶点的可改进量α，相当于标号的第二个分量 int que[maxn]; int qs,qe;//队列首尾位置坐标 int v,p;//当前顶点、保存Cij-Fij for(i=0; i<maxn; ++i) for(j=0; j<maxn; ++j) flow[i][j]=0; minflow[0]=INF;//源点标号的第二分量为无穷大 while(1)//标号法 { for(i=0; i<maxn; ++i)//每次标号前，每个顶点重新回到未标号状态 prev[i]=-2; prev[0]=-1; qs=0; que[qs]=0;//源点入队 qe=1; while(qs<qe&&prev[t]==-2) { v=que[qs];//取队列头节点 ++qs; for(i=0; i<t+1; ++i)//prev[i]==-2表示顶点i未标号 if(prev[i]==-2&&(p=edge[v][i].c-flow[v][i]))//edge[v][i].c-flow[v][i]!=0能保证i是v邻接顶点且能进行标号 { prev[i]=v; que[qe]=i; ++qe; minflow[i]=(minflow[v]<p)?minflow[v]:p; } } if(prev[t]==-2) break;//汇点t无标号，标号法结束 for(i=prev[t],j=t; i!=-1; j=i,i=prev[i])//调整过程 { flow[i][j]+=minflow[t]; flow[j][i]=-flow[i][j]; } } for(i=0,p=0; i<t; ++i)//统计进入汇点的流量即最大流的流量 p+=flow[i][t]; cout<<p<<endl; }