求最大网络流的C++实现(利用广度优先遍历的思想)

转载本博客上原创文章者，请注明出处。

基本思想：

利用广度优先遍历的思路，从一个可行流(一般取零流)开始，不断进行标号过程和调整过程，直到找不到起点到终点的可增广路径为止。

1、标号过程

在这个工程中，网络上的点分为已标号点和未标号点。将起始点标号，其他刚开始未标号。从起始点开始，利用广度优先算法进行遍历，找到一个未标号点时，看临接的标号点与之是正向边还是反向边，以此来进行相应的标号(标号就是记录下当前结点的前一个结点，还有要记录下这两个结点形成的边可增加的流量)。若所有结点都检查过去，而标号进行不下去(终点不能够标号时)，则算法结束(调整过程也不用执行)，此时的可行流就是最大流。

2、调整过程

用终点标号中可增加的流量的值，往前运动到起点，对这条路径上的结点进行调整：正向边的加上该流量值，反向边减去该流量值。接着，清除所有标号，再进入标号过程。这样重复下去。

实现程序：

#include <iostream>#include <queue>using namespace std;const int Maxn=100; //图最大的结点数int pre[Maxn]; //保存前一个结点的序号int v[Maxn]; //结点的流量的可增加量int g[Maxn][Maxn]; //表示边的最大容量int f[Maxn][Maxn]; //表示边的以用容量//求最小值的函数int min(const int val1,const int val2){return val1<val2 ?val1:val2;}//利用广度优先的思想(邻接矩阵存储)int maxFlow(){int n=0; //n表示结点数//初始化memset(v,0,sizeof(v));memset(f,0,sizeof(f));cin>>n;int s=0,t=n-1; //s为起点，t为终点for(int i=0;i<n;++i)for(int j=0;j<n;++j)cin>>g[i][j];int queTop=0; //队列的列首while(true){memset(pre,int(-1),sizeof(pre));queue<int> que;pre[s]=s;v[s]=0x7fffffff; //起点无限制que.push(s);//用广度优先搜索算法来寻找增广路while(!que.empty()){//取出队首元素queTop=que.front();que.pop();for(int i=0;i<n;++i){if(pre[i]<0) //小于0表示还没处理过{//正向边if(g[queTop][i]>f[queTop][i]){v[i]=min(g[queTop][i]-f[queTop][i],v[queTop]); //流量增加量的计算pre[i]=queTop; //前一个结点que.push(i);}//反向边if(f[i][queTop]>0){v[i]=min(f[i][queTop],v[queTop]);pre[i]=queTop+n; //反向边pre保存的是原来queTop值加n的数，方便更新时//判定是正向边还是反向边que.push(i);}}}//说明终点已经处理了，已得到一条增广矩阵，跳出循环，进入调整工作if(pre[t]>=0) break;}if(pre[t]<0) break; //说明找不到增广路经，这时的流就是最大流//调整边的剩余权值int p=0,q=t;int minval=v[t];//从终点向前用minval进行调整while(q!=s){p=pre[q];if(p>=n){p-=n;f[q][p]-=minval;//说明这条边是反向边}elsef[p][q]+=minval;//说明这条边是正向边q=p;}}//最后输出最大的流量queTop=0;for(int i=0;i<n;++i) queTop+=f[s][i];return queTop;}int main(){cout<<maxFlow()<<endl;}