网络流24题选讲

前言

CSP2021 T4 一个显然的最小割的60分做法没有看出来，特此来补一补网络流。

餐巾计划问题

题意

餐馆在第 (i) 天需要 (a_i) 块餐巾，购买餐巾需要 (p) 元，可以送去慢洗店，(t_1) 天之后拿到，洗一条的代价为 (f_1)。可以送去快洗店，(t_2) 天之后拿到，洗一条的代价为 (f_2)（(t_1ge t_2) 且 (f_1le f_2)）。

数据范围：(nle 2000)

solution

考虑费用流，一个简单的想法是每个点直接连向 (t_1) 天后和 (t_2) 天后，但是因为必须钦定每天都有 (a_i) 块餐巾，这样建图不好满足这个限制。

考虑拆点，源点连 (a) 点，代价为 (p)，流量为 (infin) ，表示买餐巾；源点 (b) 点源点，代价为 (0) ，流量为 (a_i) ，表示获得餐巾。 (b) 点连汇点，代价为 (0)，流量为 (a_i)，表示钦定使用了 (a_i) 条餐巾。 (b) 点连 (t_1) 天后和 (t_2) 天后的 (a) 点，表示洗毛巾，注意这里的连边表示必须在 (x) 天后使用，因此，我们需要把不用洗的餐巾留下，也就是 (b) 连向下一天的 (b)。

加强版 [BJWC2018]餐巾计划问题

数据范围：(nle 2 imes 10^5)

容易发现这个答案和购买的餐巾数量是一个单峰函数的关系。考虑三分购买的餐巾数量，现在只需要考虑在餐巾数量确定时，需要的最小代价。

首先餐巾一定是越靠前买越好，因为后面送洗的时间更加充裕。贪心地，我们肯定是能慢洗则慢洗，而慢洗不了的时候，只能选择快洗。显然优先选择时间更近的来快洗，因为时间更远的可以留来慢洗。

使用两个 deque 维护，单次复杂度 (O(n))，总时间复杂度 (O(nlog n))

[CTSC1999]家园 / 星际转移问题

题意

（见原题面）

solution

枚举时间，根据时间建分层图，每多建一层跑一次 dinic，无解用并查集判断。

飞行员配对方案问题&试题库问题

二分图匹配模板题

最小路径覆盖问题

题意

DAG 的最小路径覆盖（无重复点）

数据范围：(nle 150,mle 6000)

solution

拆点，原图的边在网络流里是出点连入点。同时每个点最多作为出点 (1) 次，作为入点 (1) 次。一个匹配相当于是把两条链合并到一起，所以答案是 点数(-)最大匹配。

DAG的可相交最小路径覆盖

即不用考虑中间点。Floyd 求出一个点能够到哪些点，能到的点都连边。然后就变成了不可相交的最小路径覆盖。

魔术球问题

题意

（见原题面）

solution

加起来为平方数的点连边，然后就是最小路径覆盖问题了

航空路线问题

问题转化为找两条路线。拆点，其中 (1) 号点和 (n) 号点的流量为 (2)，其余点的流量为 (1)，完了。

太空飞行计划问题

答案是 (sum-)最小割。构造方案的话需要先判断哪些仪器是要买的（和 (S) 连通），然后根据买的仪器来确定做哪些实验。

骑士共存问题

将棋盘 (2) 染色，颜色不同的格子不能相互攻击。 能够到达的点连边，答案就是二分图最大独立集。

最长k可重区间集问题

题意

(n) 个开区间，一个区间的贡献是 (r-l)，选择任意多个区间，数轴上任意一个点不能被覆盖超过 (k) 次，求最大贡献和。

数据范围：(nle 500)

solution

端点离散化，先建一个数轴，流量为 (k)，每一个区间相当于从数轴上分出一条流量为 (1) 的边。最大费用最大流即可。

最长k可重线段集问题

把开区间换成平面直角坐标系内的开线段，要求任意一条 (x=i) 的直线最多与 (k) 个线段相交，区间的代价是线段长度向下取整。

如果不存在平行于 (y) 轴的直线的话，可以直接转化为上面的问题。平行于 (y) 轴的直线带来的问题是：

1. 这个点最多有 (k) 个线段经过
2. 因为是开区间，要把端点是 (x) 的不平行于 (y) 轴的线段与端点是 (x) 的平行于 (y) 轴的线段区分出来

考虑扩域，把一个平行于 (y) 轴的直线变为 ((x imes 2,x imes 2+1))，剩下的变为((x_0 imes 2+1,x_1 imes 2))。这样就解决了上面带来的问题。

汽车加油行驶问题

按照油量建分层图，跑最短路即可。

负载平衡问题

题意

环形序列 (a_i)，一次操作可以使 (a_i-1) 并使 (a_{i+1}+1) 或 (a_i+1) 并使 (a_{i+1}-1)。求最小操作次数使得所有 (a_i) 相等。

数据范围：(nle 100)

solution

源点连需要减少的点，需要增加的点连汇点，相邻之间连边即可。跑费用流。

加强版

(nle 10^6)

设平均值为 (x​)。设 (a_i​) 给 (a_{i-1}​) 了 (b_i​)（如果 (b_i​) 为负表示 (a_{i-1}​) 给 (a_i​)）。那么可以列出方程

[egin{cases} a_1-b_1+b_2=x\ a_2-b_2+b_3=x\ cdots\ a_n-b_n+b_1=x end{cases} ]

可得

[b_2=b_1+x-a_1\ b_3=b_2+x-a_2=b_1+x-a_1+x-a_2\ cdots ]

令 (b_1) 后面的东西为 (c_i)，那么 (b_2=b_1-c_1,b_3=b_1-c_2)。

[c_1=a_1-x\ c_2=a_1-x+a_2-x\ c_p=sum_{i=1}^p a_i-xp\ c_n=0 ]

我们需要最小化 (sum_{i=1}^n|b_1-c_i|)，显然 (b_1) 取中位数最优。时间复杂度 (O(n))。