• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

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

OC/C/C++ 水墨上仙 2458次浏览

求最大网络流的C++实现(利用广度优先遍历的思想)
基本思想:
利用广度优先遍历的思路,从一个可行流(一般取零流)开始,不断进行标号过程和调整过程,直到找不到起点到终点的可增广路径为止。
1、标号过程
在这个工程中,网络上的点分为已标号点和未标号点。将起始点标号,其他刚开始未标号。从起始点开始,利用广度优先算法进行遍历,找到一个未标号点时,看临接的标号点与之是正向边还是反向边,以此来进行相应的标号(标号就是记录下当前结点的前一个结点,还有要记录下这两个结点形成的边可增加的流量)。若所有结点都检查过去,而标号进行不下去(终点不能够标号时),则算法结束(调整过程也不用执行),此时的可行流就是最大流。
2、调整过程
用终点标号中可增加的流量的值,往前运动到起点,对这条路径上的结点进行调整:正向边的加上该流量值,反向边减去该流量值。接着,清除所有标号,再进入标号过程。这样重复下去。
转自:http://blog.csdn.net/iqrocket/article/details/8350558

#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;//说明这条边是反向边
			}
			else
				f[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;
}


喜欢 (0)
加载中……