网络流专项

飞行员配对方案问题

二分图最大匹配模板, 最大流即可.

负载平衡问题

显然, 当库存比平均数大时, 这个仓库就应当向外输送货物; 反之, 这个仓库就应该接收货物. 每一个仓库都要接收货物或输出货物, 因此拆成两个点, 一个输出, 一个接收. 当库存比平均值大时, 超级源点向该点的输出点连容量为库存与平均值的差值,费用为0的边; 反之则由该点的接收点向超级汇点连容量为平均值与其库存差值,费用为0的边. 这样可以保证库存多的点输出后和库存少的点接收后库存变成平均值. 相邻的点之间输出点和接收点分别相连, 容量为 Inf , 费用为1. 由于一个仓库进出是相通的, 因此每个仓库的接收点连向输出点, 容量为 Inf , 费用为0. 跑一边最小费用最大流即可.

\(Update:\)脑子锈了, 不用拆点, 直接建图即可.(每个仓库的接收点连向输出点就相当于又合并了...)

分配问题

板题, 员工连向源点, 工作连向汇点, 中间连上费用为 c[i][j] 的边即可. 因为每人只能做一个, 因此容量都为1. 再跑最小费用最大流即可.

运输问题

与上一题类似, 但是因为不限仓库到店的个数, 而限定了仓库内的个数和店内的个数, 因此源点向仓库的连边容量为 a[i] , 店到汇点的连边容量为 b[i] , 仓库和店的连边容量为 Inf . 最小费用是板子, 最大费用可以将每天边的费用取反, 最后答案取反即可.

圆桌问题

这道题明显与前两题构图方法类似, 源点向单位连边, 容量为 r[i] 的边, 这样可以确保每个单位派出了 r[i] 的人数. 餐桌向汇点连容量为 c[i] 的边, 这样可以确保每张桌子容纳 c[i] 个人. 然后单位和桌子之间两两连容量为1的边, 因为每个单位只能向每张桌子派一人. 最后跑一遍最大流, 若最大流等于总人数, 则说明可以安排, 否则说明无解. 方案可以枚举每条由单位向餐桌的边(u, v), 若残量为0, 说明该单位u派了一名员工到餐桌v.

试题库问题

与上一题类似, 源点连问题, 容量为1, 汇点连类型, 容量为其需要的数量. 问题与其所属类型之间两两连边, 跑一遍最大流即可. 方案输出方式与上一题相同.

最长k可重区间集问题

很难想到要用网络流去解. 我们可以将整个数轴想象成一个大水管, 每个区间都是一个小水管. 当选择流过这个小水管时(区间被选取), 会分一股水流到该小水管, 然后流回来. 因为区间最多重复 k 个, 因此大水管内的流量为 k 股, 否则会出现分支大于 k , 即大于 k 的集合重叠在一起. 综上所述我们可以模拟这个方法来建图: 首先每一个位置都向后连一条边, 容量为 Inf , 费用为0的边. 这些边构建出了大水管. 然后每个区间左端点向右端点连边, 流量为1, 代表它会分出去1股水流, 费用为区间长度. 但是源点连向1, 汇点连向数轴右端点, 即 \(10^5\) 的位置. 但是经过思考我们发现只有区间的端点是有用的, 因此我们只需要将所有端点(即每个区间的左端点和右端点)按大小从小到大连起来, 再将区间左端点连向右端点即可. 源点连向最左边的端点, 容量设为 k (这是重点, 保证最多重叠 k 个区间), 最右边的端点连向源点, 跑一遍最大费用最大流即可(最大费用方法同运输问题).

餐巾计划问题

这道题改进了我对于网络流认识. 开始时我认为网络流的题可以通过建模来将题目中的某一对象类比成水流, 一单位的该元素对应一单位的水流, 求其最大流量/费用, 例如"最长k可重区间集问题", 但是如果用这种思路来解这道题, 我们将餐巾当作水流, 发现费用/容量很难设定. 比如将一天拆成早上和晚上, 源点连向每天早上, 容量为 Inf , 费用为 p , 表示购进餐巾. 早上连向晚上, 容量为 r[i] , 表示该天要用 r[i] 块餐巾, 费用为0. 晚上之间前一天连向后一天, 表示用完的餐巾可以放着. 第 i 天晚上连向第 i + m 天早上, 流量为 Inf , 费用为 f , 表示快洗. 慢洗同理. 但是注意跑最大流会使水流最大, 因此这样建图会使购买的餐巾数量最大, 实际上通过清洗我们并不需要买这么多餐巾.

问题在于我们将一块餐巾当作一股水流, 它们一一对应. 然而我们回想网络流解题的本质: 将问题中的元素抽象成点, 元素之间的约束条件用边来连接, 容量即为约束. 然后求在约束下的最大答案, 或在答案最大的前提下的最大/最小费用. 回到这道题, 一天之中早上需要新的餐巾, 晚上需要处理餐巾用过的餐巾. 两个时间段的约束是相互独立的, 因此应分别连向源点或汇点, 容量为 r[i] , 费用为0. 为什么源点连晚上, 早上连汇点呢? 因为源点向外提供, 汇点收集. 早上需要提供 r[i] 条新餐巾, 因此连向汇点, 由汇点收集. 晚上会获得 r[i] 条脏毛巾, 由源点提供, 因此由源点连向它.

对于题目中的餐巾处理方法很好处理:

• 购进: 源点连向每天早上, 容量为 Inf , 费用为 p .
• 快洗: 第 i 天晚上连向第 i + m 天早上, 容量为 Inf , 费用为 f .
• 慢洗: 方法同上.

\(Update:\) 回想一下为什么要这么建图. 因为跑费用流时是在流量最大的前提下求出的答案, 因此第一种方法会一直购进新餐巾. 所以每天所需餐巾数只能作为约束条件而不能直接等价于水流.

最长不下降子序列问题

对于第一问, 考虑网络流. 对于任意 \(i,j\) 满足 \(1 \le i < j \le n\), 若 \(x[i] \le x[j]\), 则 i 向 j 连边, 容量为1, 费用为0. 为了限制每个点只能取一次, 我们可以将每个点拆成入点和出点, 入点向出点连边, 容量为1, 费用为1(即贡献1的子序列长度). 源点连向每一个入点, 因为只取一个最长子序列, 故容量为1, 费用自然为0. 每一个出点连向汇点, 容量为1, 费用为0. 跑一遍最大费用最大流即可.

\(Update:\) 后来才反应过来这就是一个简单的最长路(因为流量为1).

对于后两个问题, 我们在第一问的基础上改进过来. 因为长度固定为最长不下降子序列的长度, 因此答案有单调性, 即我们每新找一条除去已选走的数后剩余的序列的最长不下降子序列, 发现其长度始终是减小的, 而我们要求的答案 ans , 就是使得第 ans 个剩余序列中的最长不下降子序列长度为 s , 而第 ans + 1 个小于 s . 因此我们二分答案, 每次的限定流量即为 mid (即源点连向每一个入点时容量设为 mid , 出点到汇点的边同理). 若 \(最大流下的最大费用=s \times mid\) , 则说明答案可能更大, 即left = mid + 1, 否则说明答案达不到这么大, 即right = mid - 1. 第三问在第二问的基础上将1, n 两个点的入点到出点间的流量设为 Inf 即可, 因为二者可以无限次使用. (可以推广到任意几个点可以无限次使用的情况)

但是, 这样做会超时!!! 因此可以考虑删边. 看到最长不下降子序列问题, 第一反应不是用 dp 嘛! 因此我们可以先在原序列上做一遍朴素(\(O(n^2)\))的 dp, 可以求出 f[i] 表示以第 i 位结尾的最长不下降子序列的长度. 那么我们建边时, 对于任意 \(i, j\) 不仅要满足 \(1 \le i < j \le n\) 和 \(x[i] \le x[j]\) , 还要满足 \(f[i]+1=f[j]\) 时才会建边. 这样, 建的边数就少很多啦~ 然后我们就可以快乐地切了它.