RainAir
My OI Blog
RainAir
最小费用最大流学习笔记
最小费用最大流学习笔记

最小费用最大流

定义

我想你一定学会了最大流算法
模板题链接
我们发现在同一个网络中,可能会有多个总流量相同的最大流 $f$,我们可以在计算流量的基础上,给网络中的弧增加一个单位流量的费用(简称费用),在确保流量最大的前提下总费用最小,这样的最大流叫做最小费用最大流。

https://blog.aor.sd.cn/wp-content/uploads/2018/12/1674b0b1b7889d9266c5ffdb835fd933f925af42-1.png
在上面这个网络中,弧上用逗号分隔的两个数分别为弧的容量和单位流量费用。例如,一条流量为 $2$、经过 $S \to 1 \to 4 \to T$ 的流的费用是 $(3+5+4)*2 = 24$。

做法

首先每条边多了一个属性“费用”,对于反向边怎么加呢?
我们可以这样:

接下来我们按照以下流程来实现:
1. 网络初始流量为 $0$
2. 在当前的残量网络上求出从 $S$ 到 $T$ 的最短增广路,以每条弧的单位费用为边权。如果不存在则算法结束
3. 统计答案,更改流量,重复步骤 $2$
在绝大多数情况下我们使用 SPFA 算法来求解第 $2$ 步。

代码

模型扩展

贴纸与玩偶

https://blog.aor.sd.cn/wp-content/uploads/2018/12/QQ20181208-154601.png
其中 $m \leq 100,n \leq 50$。
这个题目就是费用流经典模型了:有两种不同的属性的物品,需要找出两个不同的属性的物品进行配对并规定配对对答案的贡献。并且每种物品数量有限,要求答案最大或最小。
对于上述题目来说:源点连向每个贴纸一条流量为 $a_i$,费用为 $0$ 的弧,每个玩偶连向汇点一条流量为 $b_i$,费用为 $0$ 的弧,每个贴纸连向每个玩偶流量为 $\text{INF}$,费用为 $h_{i,j}$ 的弧,按需跑最小/大费用最大流即可。

代码

蒜头君的理发店

https://blog.aor.sd.cn/wp-content/uploads/2018/12/QQ20181208-153005.png
这一题直接看不是很好想,我们不如考虑每一个理发师对答案的贡献。
考虑一个理发师接待了 $m$ 位顾客,编号从 $1$ 到 $m$,给第 $i$ 个顾客理发需要花费 $w_i$ 的时间,那么选定一种排列方式 $p$,则该排列方式对应的答案就是 $ \sum_{i=1}^n w_{p_i} * (n-i+1) $。
那么对于每一个理发师我们可以看做是 $m$ 个状态表示,可以拆点第 $i$ 个点表示正在理倒数第 $i$ 个顾客,如果指向顾客 $j$ 表示这个顾客被这个理发师当做了倒数第 $i$ 个顾客(仅对于该理发师独立而言)。
这样建图方法就出来了:我们建立超级源点 $S$ 连向每一个理发师的每一个状态,流量为 $1$ ,费用为 $0$。每个顾客连向超级汇点 $T$ 一条流量为 $1$ 费用为 $0$ 的边。理发师 $i$ 的第 $k$ 个状态连向顾客 $j$ 一条流量为 $1$ 费用为 $k \times t_{i,j}$ 的弧。
跑一边最小费用最大流就可以求得最小总花费,进而求得最小平均花费。

代码

环游世界

https://blog.aor.sd.cn/wp-content/uploads/2018/12/QQ20181208-153849.png
题目显然可以转化为两个人,限制不能有一条边被走了两次,都到达终点的总距离最小的方案。
然后可以转换为求流量为 $2$ 时最小的费用流。
对于原图的双向边在新图中插入一条双向弧,容量为 $1$,费用为边上的距离,源点连向起点一条费用为 $0$ ,容量为 $2$ 的弧,终点连向汇点一条费用为 $0$,容量为 $2$ 的边。
考虑如何处理“容量为 $2$” 这个限制,发现这个图的特殊性质保证每次增广最多能使流量加一,所以最多增广两次即可。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/324
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

最小费用最大流学习笔记
最小费用最大流 定义 我想你一定学会了最大流算法。 模板题链接 我们发现在同一个网络中,可能会有多个总流量相同的最大流 $f$,我们可以在计算流量的基础上,给网络中的弧增加一个单位…
扫描二维码继续阅读
2018-12-08
标签
近期评论