网络流24题 简要题解

洛谷

LOJ

下面用到的 (flow,cost) 表示边的容量和费用，S表示源点，T表示汇点

AC 23/24

题解 6/23

1.餐巾计划问题

费用流

首先建立 2*n 个节点，1~n 代表每日的餐巾需求量，n+1 ~ 2*n 代表每日可以提供的脏毛巾。

从 S 到 1~n 分别连 (inf,p) 的边表示每日可以购买无限量的毛巾

从 1~n 到 T 分别连 (w[i],0) 的边表示每日需求毛巾量

从 S 到 n+i (1<=i<=n) 连 (w[i],0) 的边代表每日可提供 w[i] 的脏毛巾

从 n+i 到 i+m (1<=i<=n) 连 (w[i],f) 的边代表快洗部，慢洗同理

最后从 i 到 i+1 (1<=i<=n-1) 连 (inf,0) 的边代表洗好的毛巾可以留到下一天

2.[CTSC1999]家园

最大流

先判断是否优解，并查集合并所有飞船可到达点，判断起点终点是否联通

地球月球可看作两个特殊的空间站，然后对每个时间点都建一套全新的空间站和飞船

每个时间的飞船和停靠站(当前时间下)连 inf 的双向边，表示人可上下飞船

上一时间的飞船向当前时间的飞船连 hpi 的边，代表飞船最多可运送 hpi 的人

上一时间的空间站向当前时间的空间站连 inf 的边，表示人留在空间站不动

源点向初始时间的地球连 k 的边，表示共有 k 人需要运输

每个时间点的月球向汇点连 k 的边，表示到达终点

建完图后不断增加时间，增广，直到最大流 == k

3.飞行员配对方案问题

二分图最大匹配

用最大流做的话就是 S 向左边点连容量 1 的边，左边点向右边点能配对的连容量 1 的边，右边点向 T 连容量 1 的边

看题解说 Dinic 比 匈牙利快不知真假。。有时间测测

4.软件补丁问题

最短路(用最短路转移的dp，类似分层图)

每个点的编号 id 表示 bug 的修补的状态，即二进制上这位是 0 代表已修复，1 代表未修复，能用补丁的点之间连有向边，权值为打补丁所需时间，求个从 $2^n-1$ 到 $0$ 的最短路

注意边存不下，松弛的时候动态建边

5.太空飞行计划问题

最小割 最大权闭合子图

一般的最大权闭合子图问题：给定一个联通的 DAG，每个点有权重，选一个点就必须选以该点为出边的所有点(依赖关系)，求一个合法的选点方案使得点权和最大。

考虑最小割建模，点权为正的点为左部图，点权为负的点为又部图，S 向左部点练 wi 的边，右部图向 T 连 -wi 的边，对于原图中的边 从点 u 向点 v 连 inf 的边，记最小割为 cut，答案即为所有正点权之和减去 cut。

简单说一下个人的理解，首先新图的一个割对应着原图的一种选择方案，割掉左边的边相当于弃掉某个正权的点，割掉右边的边相当于选择某个负权点

接下来考虑方案的合法性，反证以下，假设选了 u 没选 v 且 对应原图的一个有向边：

若 u、v 分别位于新图的两侧，设w[u]>0，w[v]<0，w[u]选了则 的边存在，w[v] 未选则 的边不存在，与方案是割集矛盾

若 w[u]>0 且 w[v]>0，那么 的边存在， 的边被割掉了，显然 的边就算加回来也不会影响 S 到 T 的连通性我们可以人为的把它补回来或者求最小割自动满足

若 w[u]<0 且 w[v]<0，那么 的边不存在， 的边存在。分两种情况讨论：若 S 能到达 u，那么边 一定不存在，否则与方案是割集矛盾；若 S 不能到达 u，那么完全可以把 的边加回来(不选w[u]) 使得答案更优

最小割方案输出：在残量网络上再跑一次 bfs，设 S 能到达的点集为 A，不能到达的点集为 B，所有 A 到 B 的满流边构成一个最小割

6.试题库问题

最大流

注意每个试题只能归属于一种类型

每个试题和类型都建一个点，S 向每个试题连 1 的边，每个试题向可以归属的类型连 1 的边，每个类型
向 T 连需求量，跑个最大流。