最大网络流算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了最大网络流算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6687字，纯文字阅读大概需要10分钟。

内容图文

参考题目HDU 3549
这是一个裸题，给定流网络，直接求最大网络流。

什么是网络流？

??设流网络$G=(V,E)$G=(V,E)是一个有向图，图中每条边$(u,v)\in E$(u,v)∈E有一个非负容量值$c(u,v)\geq0$c(u,v)≥0。在所有结点中存在两个特殊结点：源节点$s$s和汇结点$t$t；源节点只出不进，汇结点只进不出。为方便起见，假设每个结点都在源节点到汇结点的某条路径上，即存在路径s~v ~t。因此流网络是连通的，并且除源节点外每个结点至少有一条进入的边。
??对于一个流网络，设$f(u,v)$f(u,v)为边$(u,v)$(u,v)上的流量，其值应当满足以下性质：

1. 容量限制：$f(u,v)\le c(u,v)$f(u,v)≤c(u,v)，即边上的流量小于该边的容量
2. 斜对称性：$f(u,v)=-f(v,u)$f(u,v)=?f(v,u)，比如说，从$u$u到$v$v流入了3，相当于从$v$v到$u$u流入了-3的流量。
3. 流量守恒：对于所有的除源点s和汇点t外的结点，$\sum f(u,v)=0$∑f(u,v)=0，即流入某一点的流量等于流出该点的流量，类似基尔霍夫定律。

最大网络流

??最大网络流的求解目的就是给定流网络，求从源点s到汇点t的最大流量，即汇点t处能获得的最大流量。同时在求解过程中要满足流量的三个性质。
??求解方法就是通过广度搜索BFS寻找一条有效路径$L$L（路径上各边的容量都严格大于0称为有效路径），然后找到这条路径上的最小残量的一条边,残量定义为$c(u,v)-f(u,v)$c(u,v)?f(u,v)，设其值为$res(u^{'},v^{'})$res(u′,v′)。由于流量限制，一条路径上的最大流量是由最小容量边决定的。然后将该路径上每条边的流量都加上这个最小值，显然，加上这个值后，该路径所有边流量都不会超过容量。
??即更新流网络，$f(u,v)=f(u,v)+res(u^{'},v^{'})((u,v)\in L)$f(u,v)=f(u,v)+res(u′,v′)((u,v)∈L)，那么在下次求残量的时候就相当于每条边容量减小了$res(u^{'},v^{'})$res(u′,v′)。更新后的网络就叫做残量网络。寻找有效路径的过程叫做找增广路经，即找到一条增广路径就意味着路径上的流量还可以增加$res(u^{'},v^{'})$res(u′,v′)，即当前结果并不是最优，汇点总流量还可以增加$res(u^{'},v^{'})$res(u′,v′)，因此最大流问题就是不断寻找增广路径，不断增加汇点流量，直到找不到一条增广路径时，此时获得的流量即为最大流。
??但是，还存在一个问题，就是更新了残量网络可能并不能达到最优，比如下面的例子（边上的数字表示该边的容量）

??对于此图如果找到1-2-3-4的路径，更新网络后为如下所示（边上的数字表示减去残量后的容量，即0表示该边不能再由流量经过）

此时汇点获得的流量为1，可以发现不能再找到一条增广路径了，因为2-3容量变为0，但是我们知道，从一开始走1-2-4和1-3-4两条路径可以有更大的最大流2，因此在此，我们要在更新网络后能够有反悔的机会，即让2-3这条边还能反向走，所以引入了反向边
??对反向边可以这样理解，以上面的例子为例，开始走1-2-3-4这条路径后，2-3边容量为0，流量为1（注：图中的边上的数字表示容量，但实际计算或者代码实现的时候容量保持不变，更新的是流量$f(u,v)$f(u,v)），然后现在我们试着走1-3-2-4这条路径，在3-2时，假设能够从3走到2，那么相当于抵消掉了原来2-3中的流量，此时2-3这条边的流量为0；然后2-4中有了单位1的流量，其实就相当于将原来2-3中的流量退回去，又送到了2-4中，而更新后3-4中的流量相当于来源于1-3中的流量，这样就很好理解了。现在我们重新来看一下上面那个例子：
首先找到第一条增广路径1-2-3-4（蓝色线所示）

然后更新各边容量（为方便起见，图中都是对容量更新，流量更新转换一下就是了）棕色线是反向容量的更新，正向容量是减，反向容量就是加，如下图：

现在可以发现，1-3-2-4这条路与开始1-2-3-4路径上的流量一致，其实正向边、反向边都是相对而言的，并没有绝对的正向与反向。于是这条路就可行，下面是按路径1-3-2-4路径走完后更新的残量网络：

??现在我们可以发现，所有能到达汇点4的路径由于容量限制，不再有增广路径，此时汇点获得的流量为最大流。对于中间2-3和3-2这两条边来说，目前更新后是以3-2为正向，所以3-2容量为0，已经流满，同时反向的容量为1，也表示流满（因为反向边初始容量为0，后面将会说明），那么正反向就互相抵消，即2-3这条路中没有流量，这跟初始状态的2、3边情况是一样的。
??那么具体如何来实现呢？可以对每次更新残量网络的时候进行正反两条边的更新，那么算法可以描述为：

• $do \ \ while$do  while
• ????找到一条增广路径$L$L，路径上每条边满足流量三个性质
• ????找到最小残量 $res(u^{'},v^{'})=min\lbrace c(u,v)-f(u,v)|(u,v)\in L\rbrace$res(u′,v′)=min{c(u,v)?f(u,v)∣(u,v)∈L}
• ????更新$L$L上每条边，得到残量网络：
• ????????正向边：$f(u,v)=f(u,v)+res(u^{'},v^{'})$f(u,v)=f(u,v)+res(u′,v′)
• ????????反向边：$f(v,u)=f(v,u)-res(u^{'},v^{'})$f(v,u)=f(v,u)?res(u′,v′)
• ????$maxflow=maxflow+res(u^{'},v^{'})$maxflow=maxflow+res(u′,v′)
• $until$until找不到增广路径
• $print(maxflow)$print(maxflow)//输出最大流
  ????在初始化的时候，对于所有正向边和反向边的流量初始化为0，因为开始没有任何流量流通。即$initial:f(u,v)=f(v,u)=0$initial:f(u,v)=f(v,u)=0显然，满足流量三个性质。然后更新的时候，正向边加上残量，流量变为正，反向边减去残量，变为负，显然，加上的和减去的是相同的值，所以满足斜对称性。值得注意的是，正向边的容量上限是$c(u,v)$c(u,v)，而反向边容量上限是0，所以在初始化容量时，有：
  ????正向边：$c(u,v)=c$c(u,v)=c
  ????反向边：$c(v,u)=0$c(v,u)=0
  当然，在寻找最小残量是公式统一都是$res=min(res,c(u,v)-f(u,v))$res=min(res,c(u,v)?f(u,v))因为即使是反向边，由于容量为0，流量为负数，相减也会得到一个正数。
  ??在寻找增广路径的时候，主要采用的是BFS搜索，当然DFS也可以，但据说大多数情况下BFS更优。下面是C++代码实现，也是例题HDU 3549的AC代码，这里运用了一个pre[i]前驱数组，用来保存i结点的前一个结点，方便在每找到一条增广路径后返回去遍历这条路径，进行各边的更新。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define inf 0xfffffff
using namespace std;
int cap[305][305];//容量
int pre[305];//记录前驱结点
int flow[305][305];//流量
int res[305];//残量 
int N,M;
queue<int>Q;
int MaxFlow()
{
    int sumflow=0;      
    memset(flow,0,sizeof(flow));
    memset(pre,0,sizeof(pre)); 
    while(1)
    {
    	memset(res,0,sizeof(res));//每一次增广都要初始残量为0
    	res[1]=inf;
    	while(!Q.empty())Q.pop();
    	Q.push(1);
    	while(!Q.empty())//BFS搜索
    	{
    		int f=Q.front();//获取队头
    		Q.pop();//队头出队
    		if(f==N)break; //找到目标点即汇点N，结束本次增广
    		for(int i=1;i<=N;i++)
    		{
    			if(!res[i]&&cap[f][i]>flow[f][i])//容量大于流量
				{
					//这里要求容量严格大于流量，所以更新后的残量
					//一定大于0，所以res[]也起标记是否访问的作用
				 	res[i]=min(res[f],cap[f][i]-flow[f][i]);
					 //取最小残量 
					 pre[i]=f;//保存前驱结点
					 Q.push(i);//入队
				}
			}
		}
		if(res[N]==0)//到汇点的所有路径最小残量为0 
			return sumflow;//无法继续更新最大流量
						//即当前获得的流量为最大流，直接返回
        int k=N,p;
        while(k!=1)
        {//利用前驱结点数组，遍历增广路径
			//更新增广路径上每条边的流量
        	p=pre[k];
        	flow[p][k]+=res[N];//正向边加上残量
        	flow[k][p]-=res[N];//反向边减去残量
        	k=p;
		}
        sumflow+=res[N];//更新总流量
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int t,k=0;
    cin>>t;
    while(t--)
    {
		memset(cap,0,sizeof(cap));//初始容量为0
        cin>>N>>M;
        for(int i=0;i<M;i++)
        {
            int x,y,c;
            cin>>x>>y>>c;
            cap[x][y]+=c;//初始正向容量
        }
        cout<<"Case "<<++k<<": "<<MaxFlow()<<endl;
    }
    return 0;
}

内容总结

以上是互联网集市为您收集整理的最大网络流算法全部内容，希望文章能够帮你解决最大网络流算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---