最小费用最大流问题
复杂网络中,单源单点的最小费用最大流算法(MCMF)应用广泛。
在实际网络问题中,不仅考虑从 Vs 到 Vt 的流量最大,还要考虑可行流在网络传送过程中的费用问题,这就是网络的最小费用最大流问题。
最小费用最大流问题的一般提法:已知容量网络 D=(V ,A ,C),每条弧 (Vi,Vj) 除了已给出容量 Cij 外,还给出单位流量的传输费用 bij≥0,记作D=(V, A, C, B),其中bij ∈B。要在费用、容量网络 D 中寻找 Vs→Vt的最大流 f={fij},且使流的总传输费用:
b(f)=Σbij fij 最小
从上一讲可知,最大流的求法就是在容量网络上从某个可行流出发,设法找到一条从 Vs→Vt 的增广链,然后沿着此增广链调整流量,作出新的流量增大了的可行流。在这个新的可行流基础上再寻找它的增广链。如此反复进行,直至再找不出增广链,就得到了该网络的最大流。
例子:给定费用、容量网络图(bij,cij),其中,bij表示费用,cij表示容量,试求网络的最小费用最大流。
解:
(1)、初始取0流量,此时总费用为 f(0) = 0。
(2)、由原始网络构建费用网络图(费用网络图每条线路上的权重为bij,bij为单位流量的费用)。
(3)、通过当前费用网络图找到一个费用最少的路径,即vs->v3->v2->vt。通过该路径上每条线段的容量得出该线路能通过的最大流量,即调整量θ = min{8,5,7} = 5,即流量为5,当前的最小费用为 f(1) = 5*1+5*2+5*1 = 20。下图为流量网络图。
(4)、在(3)的基础上构造新的费用网络图,构造方法为:当线路没流量通过时,流量方向不变,费用为原始费用。如vs->v2;
当线路流量等于该线路的最大容量时,则流量方向改变,费用为原始费用的负数。如v3->v2变为v2->v3;
当线路流量小于该线路的最大容量时,则增加反向流量,费用为原始费用的负数。如vs->v3新增v3->vs;
(5)、在(4)中得到的费用网络图上,找到费用最少的路径,即vs->v2->vt,通过该路径上每条线段的容量得出该线路能通过的最大流量,即调整量θ = min{10,7-5} = 2,得到的最小费用流的流量为7,当前的最小费用为 f(2) = 2*4+5*1+5*2+7*1 = 30。
(6)、构造可行流 f2的费用网络图。
(7)、在(6)中得到的费用网络图上,找到费用最少的路径,即vs->v3->v4->vt,通过该路径上每条线段的容量得出该线路能通过的最大流量,即调整量θ = min{8-5,10,4} = 3,得到的最小费用流的流量为10,当前的最小费用为 f(3) = 2*4+8*1+5*2+7*1+3*3+3*2 = 42
(8)、构造可行流 f3 的费用网络图。
(9)、在(8)的费用网络图上,找到费用最少的路径,即vs->v2->v3->v4->vt,通过该路径上每条线段的容量得出该线路能通过的最大流量,即调整量θ = min{10-2, 10-3, 4-3, 5} = 1,得到的最小费用流的流量为11,当前最小费用为 f(4) = 3*4+8*1+4*2+7*1+4*3+4*2 = 55
(10)、构造可行流 f4 的费用网络图。
由于无法找到从 vs->vt 的最短路,所以 f(4) 就是该网络的最小费用最大流。
相关文章
- linux修改TCP最大连接数
- 【网络流24题】最小路径覆盖问题(最大流)
- c# Linq 求和,求平均值,求最大,求最小,分组,计数
- Google Earth Engine(GEE)——feature 中使用aggregate(总计)中选取最大、最小和平均值分析
- 最大子序和
- 【BZOJ1834】[ZJOI2010]network 网络扩容 最大流+最小费用流
- 【BZOJ1877】[SDOI2009]晨跑 最小费用最大流
- hihoCoder #1127 : 二分图二·二分图最小点覆盖和最大独立集
- 【MATLAB教程案例96】基于GA优化的WSN最大覆盖率和最少节点部署数量matlab仿真
- 【多载波系统】基于多载波系统分析等比合并EGC,最大比合并MRC,正交恢复合并ORC以及最小均方误差合并MMSE的matlab仿真
- 二叉树中的最大路径和-Python
- UVaLive 6525 Attacking rooks (二分图最大匹配)
- OpenCV实现最大最小距离聚类算法
- [LeetCode]剑指 Offer 42. 连续子数组的最大和
- (第11列)C语言练习:输入数组,最大的与第一个元素交换,最小的与最后一个元素交换,输出数组。五步带你解决。
- 【创作赢红包】< 二叉树OJ题(一) >单值二叉树&&二叉树的最大深度&&翻转二叉树&&相同的树&&对称二叉树
- 全球最大单体光伏电站项目一期380兆瓦在宁并网发电
- 华为OD机试 - 求数组中最大n个数和最小n个数的和(Python) | 机试题+算法思路+考点+代码解析 【2023】
- 8.10 最大流最小割定理
- ZOJ 1654 Place the Robots(放置机器人)------最大独立集
- HDU 4862 Jump(更多的联合培训学校1)(最小费用最大流)
- 【Leetcode】215. 数组中的第K个最大元素
- 最小配置启动SQL SERVER,更改SQL Server最大内存大小导致不能启动的解决方法
- 【bzoj3130】[Sdoi2013]费用流 二分+网络流最大流