最小费用最大流问题详解

简介: 最小费用最大流问题详解

最小费用最大流问题详解

一、问题描述

在网络中求一个最大流f,使流的总输送费用最小。

image.png

伴随网络流 f 的增流网络:设 f是网络 D = ( V , A , C , F , B )的一个网络流,按照以下规则构建一个新的网络 D f = ( V , A ′ , C ′ , B ′ ) ,该网络称为伴随 f 的增流网络。

V为顶点集,A为弧集,C为容量集,F为流量集,B为费用集

image.png

image.png

负回路:在增流网络Df 中,所有的权(费用)之和小于零的回路称为负回路。

增流圈:在增流网络Df 中的负回路对应网络D中的一个圈,在这个圈中,如果方向与这个负回路方向相同的所有弧都为不饱和弧,方向与负回路方向相反的所有弧都为非零流弧,则这个圈称为增流圈。

二、求解思路

2018122814580746.png

解法I:求得最大流量调整流量分布达到最小费用

利用最大流算法,将网络的流量调整到最大流

构建伴随网络流 f的增流网络 D f

image.png

针对负回路对应网络 D中的圈,若该圈是增流圈,则把增流圈方向上与负回路方向一致的所有弧的流量加上 θ,把增流圈方向上与负回路方向相反的所有弧的流量减去 θ ;若该圈不是增流圈,则转到步骤3重新寻找负回路。

解法II:满足最小费用寻找最小费用增广链达到最大流量

image.png

三、实例

增流网络实例

有如下网络D:

2018122814580746.png

其对应的增流网络如下:

2018122814580746.png

过程:

image.png

解法I实例

实例

2018122814580746.png

首先寻找最大流,从起点出发到终点结束,将流量充满,得到最大流量图。

2018122814580746.png

然后构建增流网络

2018122814580746.png

构建好之后寻找负回路,可见这条负回路的最小容量为4,则 θ 取4

2018122814580746.png

调整原网络,可以看到对应原网络中为增流圈,与负回路与负回路方向一致的所有弧的流量加上 θ ,把增流圈方向上与负回路方向相反的所有弧的流量减去 θ得到网络 D2

2018122814580746.png

构建 D2的增流网络 Df2

2018122814580746.png

寻找负回路,发现已经找不到负回路,说明网络 D2 已经是最小费用,结束算法,得到最小费用最大流,最大流为11,最小费用为: 3 × 4 + 8 × 1 + 4 × 2 + 4 × 3 + 7 × 1 + 4 × 2 = 55

解法II实例

暂略待更


相关文章
|
3月前
|
C++
G : 最大流问题
这篇文章介绍了最大流问题的基本概念和求解方法,并通过C++代码实现了使用广度优先搜索(BFS)和残余网络来计算有向图中从源点到汇点的最大流。
|
6月前
|
算法 测试技术 C++
【大根堆】【C++算法】871 最低加油次数
【大根堆】【C++算法】871 最低加油次数
|
6月前
leetcode-871:最低加油次数
leetcode-871:最低加油次数
34 0
|
11月前
|
算法 测试技术 C++
C++前缀和算法的应用:最大化城市的最小供电站数目(一)
C++前缀和算法的应用:最大化城市的最小供电站数目
|
11月前
|
算法 测试技术 C#
C++前缀和算法的应用:最大化城市的最小供电站数目(二)
C++前缀和算法的应用:最大化城市的最小供电站数目
|
弹性计算
阿里云带宽计费模式按固定带宽和按使用流量选择计算方法
2023阿里云带宽计费模式按固定带宽和按使用流量选择计算方法,阿里云服务器公网带宽计费模式按固定带宽和按使用流量哪个划算?按固定带宽计费1M带宽一个月23元,按使用流量计费1GB流量0.8元,如果云服务器带宽使用率低于10%,那么首选按使用流量计费,如果带宽实际利用率较高的话,按固定带宽计费更划算一些。云服务器吧来详细说下阿里云服务器带宽不同计费模式下收费价格、费用计算方法及如何选择更合适说明:
351 0
阿里云带宽计费模式按固定带宽和按使用流量选择计算方法
|
算法 容器
[leetcode] 连接所有点的最小费用 -MST
这道题是最小生成树板子题 可以用并查集实现,贪心排序边权 讲一个二元组放在一个vector容器里面,其中的元素为<weight,<u,v>>对应<int,<int,int> >类型,第一个参数代表边权的大小,后面的为两个点u,v,然后按照第一个值边权从小到大排序,然后用并查集实现是否连通,从而实现最小生成树 代码有点套娃(
106 0
[leetcode] 连接所有点的最小费用 -MST
|
数据库
使用子查询统计“国内长线游”线路数、线路最高价格和线路最低价格
使用子查询统计“国内长线游”线路数、线路最高价格和线路最低价格
80 0
|
算法 C# 索引
C# 实现寻峰算法的简单优化(包含边峰,最小峰值,峰距)
原文:C# 实现寻峰算法的简单优化(包含边峰,最小峰值,峰距)   核心寻峰算法的原理参考Ronny,链接:投影曲线的波峰查找, C#翻译原理代码参考sowhat4999,链接:C#翻译Matlab中findpeaks方法  前人种树,后人乘凉。
1981 0