网络流建模

摘要

网络流算法本身不难,但是很多情况下难以被想到。其原因就在于网络流模型过于抽象,与表面的题目关联性不强。本文就从常见的建模角度,浅谈网络流建模

最大流建模

魔术球问题

有 n 根柱子,现要按下述规则在这 n 根柱子中依次放入编号为 1,2,3,… 的球:

  • 每次只能在某根柱子的最上面放球
  • 在同一根柱子中,任何 2 个相邻球的编号之和为完全平方数

求在 n 根柱子上最多能放多少个球

球是要一颗一颗放的,而我们每次放的时候,只需要考虑柱子顶端的球。所以这实际上也是一个匹配问题。

首先有一个贪心的思路(证明先咕着),就是能放就放,实在不行再开新的柱子。

而这个问题的图是动态加边的,因此对于当前考虑的点

  • 拆成 ,源点与 直接连接, 与汇点直接连接

  • 对于每个 ,我们将 连一条容量为 1 的边

我们考虑 的可用性。如果 不在某一个柱子的顶端,那么 ,也就不会重复使用 ;如果 在某个柱子的顶端,那么显然 ,这个点就可以使用。

于是在动态图上跑最大流即可。如果没有增加的流,就新开一个柱子(其实不需要特别操作,记录一下这个柱子的开头即可)

答案的输出,在最大流的过程中维护链表即可

[ZJOI2007] 矩阵游戏

允许交换给定 01 矩阵的任意两行或者两列,求能否使得某一条对角线上的数全部为 1

,多组数据

首先我们分析交换矩阵行列的性质。对于本来就在同一行的两个方格,他们经过若干次操作后,一定仍在同一行,列的情况同理。

也就是说,对于给定的 01 矩阵,其每一行列的 1 的个数是不会变化的。

对角线上的数全部为 1,也就是说要在给定的 个二元组 中找 个,满足 取遍 取遍 . 那么这就是一个完全匹配问题,直接转化为最大匹配问题即可。也就是所谓的行列匹配

最长不下降子序列问题

对一个序列做 3 个统计:

  • 最长不下降子序列的长度
  • 每个数用一次,可以不用,最多能组成多少个长度为 的不下降子序列
  • 的基础上,允许第一个数和最后一个数多次使用,求最多能组成多少个长度为 的不下降子序列

.

第一个任务, 暴力 DP 即可,定义 表示以 开头的最长不下降子序列的长度

对于第二个任务,我们尝试用流表示一个长度为 的 LIS。

构造网络流模型如下(c 表示边的容量)

  • 每个数只能使用一次,那么拆点 ,使得 .
  • .
  • .
  • .

跑一遍最大流即可

对于第三个任务,在任务 2 的基础上修改(或者直接加边)如下

  • .
  • .

再跑一遍最大流即可

[SCOI2007] 修车

现在有 个人, 辆车,一个人同一时刻只能修一辆车,第 个人修第 辆车的时间为 . 修一辆车的等待时间是从 0 时刻到该车修完时的时间。求 辆车最小平均等待时间,两位小数输出

.

显然,我们可以把问题转化为最小总时间。题面本身的信息量就比较大,因此我们尝试抽象建模。对于一个人,假设它修 辆车,修第 车的时间分别为 ,那么这 辆车的等待时间为

这个模型麻烦在于,它的求和是与这个人修的车的数量 有关的。而枚举每个人修车数量的情况显然是不现实的,因此我们尝试从另一个角度建模。我们希望所建立的模型包含的额外因素越少越好,那么首先就要消除 “总数量” 的因素。这很容易,我们把修车序列倒过来即可。假设修倒数 辆的车的时间为 ,那么等待时间为

这样的求和就方便很多了。现在我们只需要考虑每辆车给谁修,放在倒数第几个位置。注意到,第 个人倒数第 个位置上的车只能有一个,换言之用二元组 表示第 个人倒数第 个位置,那么题目中的修车方案就对应若干个 的匹配,其中 表示第 辆车。那么将修车的代价作为费用,就是最小费用最大流:

  • 二元组 映射为整数 (不会和 冲突)
  • 源点连接 连接汇点,容量都为 1,费用都为 0.
  • 对于 ,其容量为 1,费用为 .

Collector’s Problem

Bob 和他的朋友从糖果包装里收集贴纸。Bob 和他的朋友总共 n 人。共有 m 种不同的贴纸。

每个人手里都有一些(可能有重复的)贴纸,并且只跟别人交换他所没有的贴纸。贴纸总是一对一交换。

Bob 比这些朋友更聪明,因为他意识到只跟别人交换自己没有的贴纸并不是最优的。在某些情况下,换来一张重复贴纸更划算

假设 Bob 的朋友只和 Bob 交换(他们之间不交换),并且这些朋友只会出让手里的重复贴纸来交换他们没有的不同贴纸。你的认为是帮助 Bob 算出他最终可以得到的不同贴纸的最大数量。

.

我们只关心朋友有哪些贴纸,能交换的贴纸的数量,Bob 的每种贴纸的数量。我们要最大化 Bob 拥有的贴纸种类。

我们发现,Bob 与某一朋友交换某一贴纸最多一次(朋友只交换他们没有的不同贴纸)。也就是说对于 Bob 手里的第 种贴纸,它与每个朋友至多做一次交换。而 Bob 手里的不同的两种贴纸的交换是互不相关的。

Bob 给出第 种贴纸,就会换来不同的贴纸。因此每一次交换是从 Bob 开始,从 Bob 结束。把贴纸的一次转移当做一个单位的流,建模如下:

  • 对每种贴纸(包括 Bob 没有的)建立点 连边,容量为 Bob 拥有贴纸 的数量。同时 向汇点 连边,容量为 1.
  • 对 Bob 的每个朋友建立点 ,如果 没有第 种贴纸,就 连一条容量为 1 的边,表示 Bob 可以向朋友 转移一张贴纸;如果 张贴纸 ,就 连一条容量为 的边,表示 最多向 Bob 转移 张贴纸 .

在这样的模型下,对于 Bob 已有的贴纸,它们可以直接 来表示 Bob 已有;对于 Bob 没有的贴纸,它们会从 Bob 某个盈余的贴纸 开始转移,直到转移到另一个他没有的贴纸 ,使 Bob 手里的贴纸种类增加。

小结

利用最大流建模,一般从多个角度分析问题因素:

  1. 信息的提取与转化
  2. 对象的独立性、唯一性与性质分析
  3. 流的意义与权重
  4. 是否涉及到动态的维护

最小割建模

图的割是一个边集 ,将这个边集内的边去掉后,图不连通。最小割的含义是容量最小的割。根据最大流最小割原理,我们可以将问题的模型转化为最小割模型,然后用最大流来求解。

方格取数问题

Luogu2774

给一个 的矩阵,每个方格上有一个数字,要求选取若干不相邻(对角线的不算相邻)的方格并最大化权值和

.

要使选取的权值和最大,就要使不选取的权值和最小。考虑到方格只影响与其相邻的方格,则将方格作为结点,相邻的方格连边。那么一条边的两个端点不能同时选取。由于这个图是一个二分图,相当于可以黑白染色,那么黑白点分别连接源点汇点,相邻的点建立连边

我们需要找到一个最小割使得图不连通。思考这个割的意义,我们发现,如果你割掉源点连接黑点的边或者白点连接汇点的边,相当于你不选这个点,但如果割掉相邻黑白点的连边,这对于题目中的选择方案是没有意义的。我们希望我们的最小割等价于题目中的最优选取方案,那么就要禁止无意义的方案。因此把这类边容量设为 INF 即可。

  • 建立源点汇点
  • 源点连接黑点,容量为点权;白点连接汇点,容量为点权
  • 黑点连接相邻的白点,容量为 INF

就可以利用最大流来求解最小割了

[NOI2006] 最大获利

公司得到了一共 个可以作为通讯信号中转站的地址,建立第 i 个通讯中转站需要的成本为 . 另外公司调查得出了一共有 M 个用户群,第 i 个用户群的信息概括为 :这些用户会使用中转站 和中转站 进行通讯,公司可以获益 .

公司可以有选择的建立一些中转站(投入成本),为一些用户提供服务并获得收益(获益之和)。那么如何选择最终建立的中转站才能让公司的净获利最大呢?(净获利 = 获益之和 – 投入成本之和)

对于第 个中转站建立点 ,建立源点到 的边,容量为 . 割掉这条边表示建立这个中转站。

对于第 个用户建立点 连接汇点,容量为 . 割掉这条边表示不满足这个人的需求。

如果第 个用户可能使用第 个中转站,就从 连一条边,容量为 INF. 即,割这条边在原问题中没有意义。上面的两种边足以包含整个题目的可变信息,而 是常量信息,并且两两一组,不容易抽象为边的模型,因此我们不考虑割这种边。

思考这个图的一个割的意义,相当于我们建立某些中转站,同时又会放弃某些人的需求,最后使得花费的钱最少。那么用总的收益减掉花去的钱(最小割)即可。

Course Selection

Codechef Dec14

2019.5.1 更新

课业计划一共有 n 项课程,每项课程都要在 m 个学期内的某一个完成。有 组课程 要求 完成学期的前面完成。

对于课程 ,在不同的学期完成的得分不同。令 表示课程 i 在学期 j 完成的得分,如果 ,表示学期 j 中没有开设课程 i。求每个课程分数的最大平均值。

.

最大平均值就是最大总和,就是最小扣分,我们取得分的相反数就是扣分。如果没有开设课程,那么扣分就是 .

如何建立最小割模型?这就要看如何来定义割的东西。如果割的是边,那么就是割掉课程 i 和学期 j 的边。但是这样建立的模型是无法达到最小割的效果的,因为你删除一条边后,剩下的 m-1 的条边仍然是连通的,整个图很难被割为两个部分。

如果割的是点,那么我们定义点 表示课程 i 在学期 j 上。割掉点的意思就是割掉这个点代表的状态。进行如下建图:

  • 源点连接 ,容量为 .
  • 连一条边,容量为 .
  • 向汇点连边,容量为 .

割掉连入 的边,表示课程 i 在学期 j 学习。这样建模就是不考虑 k 组课程顺序的情况下的最小扣分。若 a 是 b 的前置课程,那么 a 割边的位置要在 b 割边的位置的前面。因此一但 a 割边的位置在 b 的后面,那么 a 和 b 的子图不能被割断,从这个角度思考,建模如下:

  • 从源点向 连边,容量为 .
  • 连边,容量为 .

至于负容量,先给他们加上一个基础值 让他们全部为正,求完最小割后再减回来即可。

Happiness

2019.5.2 更新

高一一班的坐位是一个 的矩阵,经过一个学期的相处,每个同学和前后左右相邻的同学互相成为了好朋友。这学期要文理分科,每个同学选理科的喜悦值是 ,选文科的喜悦值是 .

一对好朋友如果同时选理科,他们将一共获得喜悦值 ,如果同时选文科,将一共获得喜悦值 . 问如何选择可以使全班喜悦值总和最大。

.

首先,连源点的边表示选理科,连汇点的边表示选文科。把得分理解为扣分,那么选文科就会扣掉选理科的分,我们要让扣分最小。先考虑两个人的情况,我们在两个人之间连边

p1

假设 AB 同选理科获得的喜悦值是 x,同选文科获得的喜悦值是 y,我们现在只考虑 的分布。如果两个人同时选理科,就割掉 c,d;如果同时选文科就割掉 a,b,如果 A 选文 B 选理就割掉 a,d 和方向向上的 e;如果 A 选理 B 选文就割掉 b,c 和方向向下的 e. 因此

那么由 得到

那么我们可以这样建模

建边 含义
是所有与 i 相邻的同学选理科的喜悦度总和
同理
相当于建立双向边

The Year of Code Jam

Google Code Jam 2008 Final E

一个 的矩阵中有黑白灰三种颜色的格子。灰色的格子可以变成黑色或者白色的格子,不能不变。一个黑色格子的收益为 4,但是如果有两个黑色格子相邻,那么这两个黑色格子的收益都减 1. 问最大收益。

p1

这道题的收益关系仍复杂,因此先分析两个格子的情况。我们把 ans 初始化为所有灰色格子都是白色时的总收益,加上灰色格子数的 4 倍。

对于灰色格子:

  1. 变成白色格子,那么贡献减 4.
  2. 变成黑色的格子,如果周围一开始就有 t 个黑色格子,那么贡献减 2t。

而对于两个相邻的灰色格子,如果同时变成黑色,那么贡献减 2.

p2

在这个模型中,源点汇点分别代表黑色还是白色并不重要,因此我们不对此做区分。而且为了保证在同时选择黑色的时侯割掉 A-B 的边,必须使 A 和 B 的黑白边的位置相反。如果 2t 的边位于同侧,就没有办法割掉中间的边了。

推广到多个灰色格子,我们需要让所有相邻的灰色格子都这样错位建边。由于这个图是个二分图,因此可以达到。

小结

上述模型一是利用了 INF 的边来限制模型的条件,避免出现无意义的状态。使用这样的边也可以将题目中的约束条件转化到图上(因为 的边不能割),从而求解出正确的结果。

二是对于收益关系复杂的问题,先考虑两个人的情况,再把所有关系综合起来考虑。

参考文献

姜志豪,《网络流的一些建模方法》,国家集训队 2016 论文集。


  转载请注明: Sshwy's Blog 网络流建模

 上一篇
杂题整理 杂题整理
摘要 水题泛做 ZROIZROI332 摆花 对于一个整数序列和 m 个区间,定义序列的某一区间 的价值为 (即 sg 函数的 mex). 而这个序列的价值定义为这
2019.03.05
下一篇 
构造题自闭 构造题自闭
摘要 鸽鸽给我们讲课啦 竞赛中有一类要求构造特定解的题,被称为构造题 构造题没有固定的套路,它要求选手对该领域知识有深层次的理解 URAL1979 对于一个 阶的魔方,要求把
2019.03.02
  目录