最小费用最大流问题详解

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

最小费用最大流问题详解

一、问题描述

在网络中求一个最大流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 最低加油次数
|
11月前
|
算法 测试技术 C++
C++前缀和算法的应用:最大化城市的最小供电站数目(一)
C++前缀和算法的应用:最大化城市的最小供电站数目
|
11月前
|
算法 测试技术 C#
C++前缀和算法的应用:最大化城市的最小供电站数目(二)
C++前缀和算法的应用:最大化城市的最小供电站数目
|
索引
leetcode 寻找峰值
峰值元素是指其值严格大于左右相邻值的元素。 给你一个整数数组 nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。
|
算法 容器
[leetcode] 连接所有点的最小费用 -MST
这道题是最小生成树板子题 可以用并查集实现,贪心排序边权 讲一个二元组放在一个vector容器里面,其中的元素为<weight,<u,v>>对应<int,<int,int> >类型,第一个参数代表边权的大小,后面的为两个点u,v,然后按照第一个值边权从小到大排序,然后用并查集实现是否连通,从而实现最小生成树 代码有点套娃(
105 0
[leetcode] 连接所有点的最小费用 -MST
|
算法
岛屿的数量
前言 文本已收录至我的GitHub仓库,欢迎Star:github.com/bin39232820… 种一棵树最好的时间是十年前,其次是现在
109 0
200.岛屿数量
200.岛屿数量
89 0
200.岛屿数量
LeetCode 5958. 股票平滑下跌阶段的数目(滑动窗口)
LeetCode 5958. 股票平滑下跌阶段的数目(滑动窗口)
185 0