注,以下内容中,连边(x,y,z)(x, y, z)表示从xxyy连流量为zz的边

最大流

Algorithm

只会Dinic

无源汇上下界可行流

这篇文章写得很好

设一条边给出的为(x,y,L,R)(x, y, L, R)

新建超级源SS,超级汇TT,然后把下界去掉

感性理解,假设从xxyy已经流了LL的流量了,那么xx \rightarrow还能再流RLR - L这么多流量

又因为要保证流量平衡,所以xx要流出去LL的流量,yy要流入LL的流量,于是连(S,y,L)(S, y, L)(T,x,L)(T, x, L)即可

跑一边SSTT的最大流,若SS的出边全满流则说明有解,方案很容易根据残留网络构造

有源汇上下界最大流

假设给定的源汇为 ,新建超级源SSSS和超级汇TTTT

先连(T,S,inf)(T, S, inf)的边把SSTT流量平衡,转化成无源汇的问题

仿照上面的方法求出一组可行流,再从SSTT跑一次最大流即为答案

因为第二遍跑的时候会把TST \rightarrow S这条边的流量退回去(若存在),所以第二遍跑出来的答案就是最终答案,不用管第一次的

有源汇上下界最小流

和最大流同理,第二遍从TTSS跑最大流即可

直接应用

POJ1149 PIGS

mm 个猪圈,第 ii 个原本有 AiA_{i} 头猪。

nn 个顾客,第 ii 个顾客可以打开几个指定的猪圈,并且最多得到 BiB_{i} 头猪,在每一个人购买完成之后,被打开的猪圈中的猪可以在被打开的猪圈中任意分配,然后又会在下一个顾客到来之前把所有猪圈关上。

问最多能卖出的猪的总数。

n100,m1000,Ai1000n \le 100, m \le 1000, A_{i} \le 1000

Solution 把顾客看成点,第ii个顾客向TT(i,T,Bi)(i, T, B_i)的边

对于每个ii猪圈考虑,设 的顾客能打开这个猪圈

连边(S,p1,A[i])(S, p_1, A[i]), 2jk,(pj1,pj,)\forall 2 \le j \le k, (p_{j - 1}, p_j, \infty)

矩阵行列限制

限制与行/列的和相关

把行列看成点,分成左右两部分,A(i,j)A_{(i, j)}的数就从左部的ii连向右部的jj

LG P4194 矩阵

给定一个矩阵A[n×m]A[n \times m],求一个矩阵B[n×m]B[n \times m],满足Bi,j[L,R]B_{i, j} \in [L, R],且最小化:

20-3-20-1

Solution 枚举/二分答案 midmid ,问题转化为判定是否存在矩阵 BB 使得式子小于等于 midmid 。具体而言,第 ii 行满足 mid+jAi,jBi,jmidjAi,j-mid + \sum_{j}A_{i,j}\le B_{i,j} \le mid - \sum_{j}A_{i,j} ,第 ii 列同理

行列抽象成点,从源点往每一行连这样限制的边,从每一列往汇点连这样限制的边。然后再从每一行往每一列连 [L,R][L,R] 的边。跑有源汇点上下界可行流即可

路径覆盖

DAG最小路径覆盖,最小链覆盖,最长反链等

link

LOJ #6003.「网络流24题」魔术球问题

nn 个柱子上依次放入编号为 1,2,3,...1, 2, 3, . . . 的球,限制每次只能在柱子最上面放球,并且任意两个位置相邻的球的编号之和要是完全平方数。问最多能放多少球。

n55n \le 55

Solution 枚举/二分答案,按两个球是否能相邻的关系建图,问题转化为计算需要多少个柱子才能放入所有球。因为放入的球编号递增,故此图为 DAG 。

求 DAG 的最小路径覆盖即可。

时间分层

二分答案/枚举答案,按时间维建出分层图

#6015. 「网络流24题」星际转移问题

nn 个地点和 mm 艘飞船。每艘飞船的移动路径是一个连接若干地点的环,飞船在两个地点之间的移动耗时均为 11 。飞船有容量。问 kk 个人从 11 号地点全部移动到 nn 号地点的最小时间。

m13,n20,k50m \le 13, n \le 20, k \le 50

Solution 建分层图,移动一层代表时间加 11

在每一层,从每个结点往下一层的该结点连 inf\inf 的边,如果有一条 (u,v,w)(u, v,w) 的飞船移动路径,就从 uu 往下一层的 vvww 的边。然后从第一层的 11 开始往最后一层的 nn 跑最大流,满流即可行。

这里二分时间每次重新建图反而还不如每次暴力在残量网络的基础上新增一层,然后更新最大流。

LG P3191 HNOI2007 紧急疏散EVACUATE

Solution 和上一题类似,但注意这里不能暴力连边(每个格子往周围四个格子连边),而应该bfs预处理每个人到每个门的最短路,然后连边

回路限制

混合图欧拉回路

我们的目标是使得每个点的出入度之差归于 00 。可以先把无向边任意定向再调整。考虑边 (xy)(x \rightarrow y) 被反向之后会产生的影响:xx 的出入度之差减少 22yy 的增加 22

从源点往所有出度 >> 入度的点连容量为差的边,从所有入度 >> 出度的点往汇点连容量为 |差| 的边,再对于被定向为 (xy)(x \rightarrow y) 的无向边,从 xxyy 连容量为 22 的边。跑最大流,判断是否满流即可。

所有形如 "第 ii 个点上有 aia_{i} 个人,边有长度 / 费用 / 通过人数限制,求让第 ii 个点有 bib_{i} 个人的最小代价 / 是否可行" 这样的题,都可以用类似的方法解决。

最大权闭合子图

闭合子图:有向图的一个点集 AA,满足对于任意一条 (ab)(a \rightarrow b) 的边而言,要么 a,ba, b 同属于 AA ,要么同不属于 AA

在点权存在正负的情况下,求解最大权闭合子图需要用到网络流。

从源点向所有正权点连流量为其权值的边,从所有负权点向汇点连流量为其权值相反数的边,对于原图中的边 (ab)(a \rightarrow b) ,从 aabb 连流量为 inf\inf 的边。

我们把割一条与源点相连的边认为是放弃它的权值,割一条与汇点相连的边认为是接受它的代价。

那么一个闭合子图的权值 = 原图的正权点之和 - 被割的正权点 - 被割的|负权点|。

也就是说,原图闭合子图的最大权 = 原图的正权点之和 - 新图的最小割。

LG P3749 六省联考2017 寿司餐厅

solution

平面图转对偶图

平面图的最小割即为对偶图的最短路

距离限制

LG P3227 HNOI2013 切糕

一个n×mn \times m的网格,每个位置有rr种选择,编号为11rr,每种选择有对应代价,每个位置要恰好选一种

限制每个点和它上下左右相邻的四个点的选择编号相差均不能超过dd,最小化总代价

Solution 建图最小割

对每个点建出一条r+1r + 1个点的链,中间的rr条边对应rr种选择的代价,割边就代表选择

ii链和jj链选择的编号相差不能超过dd,就从ii链的第dxr\forall d \le x \le r个点往jj链的第xdx - d个点连\infty的边,再反着建一次

20-3-29-1

Hall定理

link

LG P3679 CERC2016 二分毯 Bipartite Blanket

AA为左部的某个子集,BB为右部的某个子集,那么有性质:

AA被至少一个匹配覆盖,BB被至少一个匹配覆盖,则ABA \cup B至少被一个匹配覆盖

然后状压DP + Hall定理分别预处理左右部的哪些子集合法,然后two pointers合并即可

费用流

我只会spfa费用流,并且下面的题题意也懒得放了

直接应用

LG P4068 [SDOI2016]数字配对

转化题意,两个数xyx \le y可以配对,当且仅当yyxx的倍数且yy的质因数指数之和 = xx的质因数指数之和 +1

由此可见构建出来的图是二分图,费用流不断增广至收益<0 < 0

UVA1104 芯片难题 Chips Challenge

Solution 从大到小枚举总零件数量,行列建二分图,三种不同的插槽通过上下界来限制

但是这样无法限制第ii行和第ii列的零件数量相等

考虑引入费用,用流量来限制行列零件数量相等: 在第ii行和第ii列间连(,0)(\infty, 0)的边,而之前每个零件对应的边增设费用为1

此时最大流必然是满流,而为使流量最大,(,0)(\infty, 0)边的两端点其余流量之和必然相等,满足了上述条件。跑上下界最大费用最大流即可

有一个小技巧可以去掉下界:把必须要流的边的费用设为一个大数limlim,然后看最大费用包含了多少个limlim<br>

回路限制

和最大流类似

LG P3965 TJOI2013 循环格

Solution 题意转化为,保证每个格子入度和出度都为11。出度已经保证,只需保证入度

左边箭头右边点,考虑每个箭头会影响哪些点的入度,若方案改变则增设费用为1

二分图最小权匹配

费用递增

这类问题通常是一个物品可以选择多次,而每次选择的代价递增。

最小费用最大流必然优先选择代价较小的边,所以不用管边的顺序问题,符合要求

LG P2050 NOI2012 美食节

Solution 考虑每个厨师的第ii道菜对答案的贡献。

设这个厨师一共做了ss 道菜,那么第ii道菜的贡献 = 做菜时间 ×(si+1)\times (s - i + 1)

注意到费用递减,且我们不知道 ss 的值

倒过来考虑,考虑每个厨师倒数第ii道菜对答案的贡献,贡献 = 做菜时间 ×i\times i。费用递增,最小费用最大流符合要求

把每个厨师拆成pp个点,第ii个点表示倒数第ii道菜,限制容量为11即可

但是直接跑边数太多,无法通过。考虑动态开点(因为每个厨师每次增广最多被选择一次),每个厨师的点一开始只拆一个出来。若被增广到了再新开点

LG P4307 JSOI2009 球队收益

Solution Di=0D_i = 0,而因为Ci0C_i \ge 0,所以一个球队赢的场数乐队,每多赢一场获得的收益越大,符合模型

每场比赛和双方球队连边,容量为1,一条增广路代表一个获胜事件

Di0D_i \ne 0时,不妨先假设每场比赛双方全输,每场比赛会使一个球队多赢一场且少输一场

设第ii个球队当前赢aa场,输bb场,则球队多赢一场比赛的收益增量为

$

所以aa越大,bb越小,多赢一场比赛的收益增量越大

直接套用模型即可

签到问题

这类问题通常会限制必须遍历一些点,或一些点必须遍历多少次。

把每个点拆成 22 个点,一个点T\rightarrow T, SS\rightarrow另一个点

TT相连的点视为到此签到,和SS相连的点视为从此出发。

LG P1251 餐巾计划问题

Solution 每天拆成两个点AiA_iBiB_i,设这一天餐巾需求量为xx

1. AiA_iTT连边(x,0)(x, 0),表示签到

2. SSBiB_i连边(x,0)(x, 0),表示签到后剩下了xx块餐巾可以再利用

提供餐巾的方式:

1. 购买餐巾: (S,Ai,,p)(S, A_i, \infty, p)

2. 快洗: (Bi,Ai+m,,f)(B_i, A_{i + m}, \infty, f)

3. 慢洗: (Bi,Ai+n,,s)(B_i, A_{i + n}, \infty, s)

4. (Bi,Bi+1,,0)(B_i, B_{i + 1}, \infty, 0)

最小费用最大流

LG P2469 SDOI2010 星际竞速

Solution 类似最小路径覆盖问题,每个点拆成Ai,BiA_i, B_i

1. (Ai,T,1,0)(A_i, T, 1, 0)表示到这个点签到

2. (S,Bi,1,0)(S, B_i, 1, 0)表示签完到从这个点出发

3. (S,Ai,1,ai)(S, A_i, 1, a_i)表示瞬移

4. 对于原图一条边(x,y,z)(x, y, z),连(Bx,Ay,1,z)(B_x, A_y, 1, z)表示经过这条边

最小费用最大流