网络流 24 题集锦及解析

• 2018-05-01
• 0
• 4

网络流 24 题题目列表

网络流 24 题题目解析

#01 飞行员配对方案问题

• 二分图最大匹配模板题，按如下方式连边：
  • 对于每一个外籍飞行员 i，连边 ( S -> i, cap = 1 )
  • 对于每一个英国飞行员 j，连边 ( j -> T, cap = 1 )
  • 若外籍飞行员 i 能与英国飞行员 j 配合，连边 ( i -> j, cap = 1)
• 答案为最大流。

#02 太空飞行计划问题

• 最大权闭合子图模板题，按如下方式连边：
  • 对于每一个收益为 v 的实验 i，连边 ( S -> i, cap = v )
  • 对于每一个价格为 v 的器材 j，连边 ( j -> T, cap = v )
  • 若实验 i 需要用到器材 j，连边 ( i -> j, cap = +∞ )
• 答案为实验收益总和减去最大流，证明略。

#03 最小路径覆盖问题

• 最小路径覆盖问题可转化为二分图最大匹配来做，按如下方式连边：
  • 将每个节点拆成两个点 i 与 i'，连边 ( S -> i, cap = 1 ) 以及 ( i' -> T, cap = 1 )
  • 对于原图上的每条边 i -> j，连边 ( i -> j', cap = 1 )
• 每个匹配对应两个可在一条路径上的点，所以答案为总点数减去最大流。

#04 魔术球问题

• 可以构造最小路径覆盖问题模型，按如下方式连边：
  • 将每个球拆成两个点 i 与 i'，连边 ( S -> i, cap = 1 ) 以及 ( i' -> T, cap = 1 )
  • 按编号从小到大依次加入球 i，对于所有编号比 i 小且能与 i 组成完全平方数的球 j，连边 ( j -> i', cap = 1)
• 每次计算最大流的增量，当增量为 0 时新开一个柱子直到柱子用完，答案即为此时加入的球数。

#05 圆桌问题

• 二分图多重匹配模板题，按如下方式连边：
  • 对于每个代表数为 v 的单位 i，连边 ( S -> i, cap = v )
  • 对于每个可做 v 人的圆桌 j，连边 ( j -> T, cap = v )
  • 对于每个单位 i 和圆桌 j，连边 ( i -> j, cap = 1 )
• 答案为最大流。

#06 最长不下降子序列问题

• 记 f[i] 表示前 i 个数所能组成的最长不下降子序列长度，可以 DP 求出。
• 对于第一问，答案 s 即为 f[i] 中的最大值。
• 对于第二问，按如下方式连边：
  • 将每个数拆成两个点 i 与 i'，连边 ( i -> i', cap = 1 ) 以限制每个数只取一次
  • 对于每个满足 f[i] == 1 的点 i，可将其作为序列首，连边 ( S -> i, cap = 1 )
  • 对于每个满足 f[i] == s 的点 i，可将其作为序列尾，连边 ( i' -> T, cap = 1 )
• 答案为最大流。
• 对于第三问，在第二问的基础上增加两条边 ( 1 -> 1', cap = +∞ ) 以及 ( n -> n', cap = +∞ )，以取消第一个数及最后一个数只取一次的限制。答案为当前最大流。

#07 试题库问题

• 二分图多重匹配模板题，连边方式与 #05 圆桌问题 类似。

#08 机器人路径规划问题

• 本题是网络流 24 题中唯一的未解难题。
• 据说有一种 O(n⁹) 的缓慢的网络流算法，以及一种 O(n⁶) 的动态规划算法，但均不能通过此题。
• 可用随机化算法，牺牲正确性以获得高分，或可通过此题。

#09 方格取数问题

• 二分图最大点权独立集模板题，首先将棋盘黑白染色，然后按如下方式连边：
  • 对于每个权值为 v 的黑点 i，连边 ( S -> i, cap = v )
  • 对于每个权值为 v 的白点 j，连边 ( j -> T, cap = v )
  • 对于每个黑点 i 及其四周的白点 j，连边 ( i -> j, cap = +∞ )
• 答案为权值和减去最小割。

#10 餐巾计划问题

• 构造最小费用最大流模型，按如下方式连边：
  • 将每一天拆成两个点 i 与 i'，分别表示当天早上 (干净餐巾) 和晚上 (脏餐巾)
  • 对于每一天 i，若需要使用 v 条餐巾，连边 ( S -> i', cap = v, cost = 0 ) 以及 ( i -> T, cap = v, cost = 0 )，表示每天晚上获得 v 条脏餐巾，每天早上消耗 v 条干净餐巾
  • 对于每一天 i，连边 ( S -> i, cap = +∞, cost = p )，表示花费 p 分/条购买餐巾
  • 对于每一天 i，若 i + m ≤ N，连边 ( i' -> [i + m], cap = +∞, cost = f )，表示花费 f 分/条将餐巾送去快洗
  • 对于每一天 i，若 i + n ≤ N，连边 ( i' -> [i + n], cap = +∞, cost = s )，表示花费 s 分/条将餐巾送去慢洗
  • 对于每一天 i，若 i < N，连边 ( i' -> [i + 1]', cap = +∞, cost = 0 )，表示将当天的脏餐巾留到下一天
• 答案为最大流量下的最小费用。

#11 航空路线问题

• 构造最大费用最大流模型，按如下方式连边：
  • 将每个城市拆成两个点 i 与 i'，连边 ( i -> i', cap = 1, cost = 1 )
  • 连边 ( S -> 1', cap = 2, cost = 1 ) 以及 ( N -> T, cap = 2, cost = 1 )
  • 对于每条航线 i -> j，连边 ( i' -> j, cap = 1, cost = 0 )
• 当最大流为 2 时，答案为最大费用减去 2
• 否则若城市 1 和 N 有直达航线，答案为 2，即 1 -> N -> 1
• 否则答案为 "No Solution!"

#12 软件补丁问题

• 状压 B1[], B2[], F1[], F2[] 跑最短路即可。

#13 星际转移问题

• 首先用并查集判断地球和月球是否连通。
• 构造最大流模型，从小到大枚举天数 d，按如下方式连边：
  • 连边 ( S -> [第 d 天的地球], cap = +∞ ) 以及 ( [第 d 天的月球] -> T, cap = +∞ )
  • 对于地球和每个太空站 i，连边 ( [第 d - 1 天的 i] -> [第 d 天的 i], cap = +∞ )，表示可以留在原地等待
  • 对于每艘载客量为 p 的太空船，连边 ( [第 d - 1 天的位置] -> [第 d 天的位置], cap = p )
• 答案即为最大流达到人数 k 时的天数。

#14 孤岛营救问题

• 状压当前拥有的钥匙跑最短路即可。

#15 汽车加油行驶问题

• 按剩余油量建立 K + 1 层图，连边跑最短路即可。

#16 数字梯形问题

• 构造最大费用最大流模型。
• 对于规则一（点和边均不重复经过），按如下方式连边：
  • 将每个点拆成两个点 i 与 i'，若其权值为 v，连边 ( i -> i', cap = 1, cost = v )
  • 对于每个第一行的点 i，连边 ( S -> i, cap = 1, cost = 0 )
  • 对于每个最后一行的点 i，连边 ( i' -> T, cap = 1, cost = 0 )
  • 对于每个非最后一行的点 i 以及其可直达的点 j，连边 ( i' -> j, cap = 1, cost = 0 )
• 对于规则二（点可重复经过），按如下方式连边：
  • 不进行拆点
  • 对于每个第一行的权值为 v 的点 i，连边 ( S -> i, cap = 1,  cost = v )
  • 对于每个最后一行的点 i，连边 ( i -> T, cap = +∞, cost = 0 )
  • 对于每个非最后一行的点 i 以及其可直达的权值为 v 的点 j，连边 ( i -> j, cap = 1, cost = v )
• 对于规则三（点和边均可重复经过），只需将规则二的边改为 ( i -> j, cap = +∞, cost = v ) 即可
• 三种规则答案均为最大流量下的最大费用。

#17 运输问题

• 构造最小（大）费用最大流模型，按如下方式连边：
  • 对于每个拥有 a 单位货物的仓库 i，连边 ( S -> i, cap = a, cost = 0 )
  • 对于每个需要 b 单位货物的零售商店 j，连边 ( j -> T, cap = b, cost = 0 )
  • 对于每个仓库 i 和零售商店 j，若单位货物运费为 c，连边 ( i -> j, cap = +∞, cost = c )
• 答案为最大流量下的最小（大）费用。

#18 分配问题

• 二分图最大完美匹配模板题，按如下方式连边：
  • 对于每个工人 i，连边 ( S -> i, cap = 1, cost = 0 )
  • 对于每件工作 j，连边 ( j -> T, cap = 1, cost = 0 )
  • 对于每个工人 i 和工作 j，若效益为 c，连边 ( i -> j, cap = 1, cost = c )
• 答案为最大流量下的最小（大）费用。

#19 负载平衡问题

• 令权值的平均数为 ave。构造最小费用最大流模型，按如下方式连边：
  • 对于每个仓库 i，连边 ( i -> [i % n + 1], cap = +∞, cost = 1 ) 以及 ( [i % n + 1] -> i, cap = +∞, cost = 1 )
  • 对于每个库存 a 满足 a > ave 的仓库 i，连边 ( S -> i, cap = a - ave, cost = 0 )
  • 对于每个库存 a 满足 a < ave 的仓库 i，连边 ( i -> T, cap = ave - a, cost = 0 )
• 答案为最大流量下的最小费用。

#20 深海机器人问题

• 构造最大费用最大流模型，按如下方式连边：
  • 对于每一条价值为 c 的边 i -> j，连边 ( i -> j, cap = 1, cost = c ) 以及 ( i -> j, cap = +∞, cost = 0 )
  • 对于每个起点 i，若有 k 个机器人从该点出发，连边 ( S -> i, cap = k, cost = 0 )
  • 对于每个终点 i，若有 r 个机器人到该点结束，连边 ( i -> T, cap = r, cost = 0 )
• 答案为最大流量下的最大费用。

#21 最长k可重区间集问题

• 首先计算各区间长度 len，然后将 r 自减 1，并对 l, r 坐标进行离散化，记离散化后的值域为 c。
• 构造最大费用最大流，按如下方式连边：
  • 连边 ( S -> 1, cap = k, cost = 0 ) 以及 ( c -> T, cap = k, cost = 0 )
  • 对于满足 1 ≤ i < c 的每个点 i，连边 ( i -> [i + 1], cap = k, cost = 0 )
  • 对于每个原长度为 len 的区间 (l, r]，连边 ( l -> r, cap = 1, cost = len )
• 答案为最大流量下的最大费用。

#22 最长k可重线段集问题

• 首先计算各区间长度 len，然后对 x 坐标进行离散化，记离散化后的值域为 c。
• 构造最大费用最大流模型，按如下方式连边：
  • 由于存在垂直于 x 轴的线段，需将每个 x 值拆成两个点 i 与 i'，连边 ( i -> i', cap = k, cost = 0 )
  • 连边 ( S -> 1, cap = k, cost = 0 ) 以及 ( c' -> T, cap = k, cost = 0 )
  • 对于满足 1 ≤ i < c 的每个点 i，连边 ( i' -> [i + 1], cap = k, cost = 0 )
  • 若原长度为 len 的开线段的两个端点 x 坐标相同，连边 ( x -> x', cap = 1, cost = len )
  • 否则令两个 x 坐标中较小值为 x₁，较大值为 x₂，连边 ( x₁' -> x₂, cap = 1, cost = len )
• 答案为最大流量下的最大费用。

#23 火星探险问题

• 构造最大费用最大流模型，按如下方式连边：
  • 将每个点拆成两个点 i 与 i'，连边 ( S -> 1, cap = C, cost = 0 ) 以及 ( [P * Q]' -> T, cap = C, cost = 0 )
  • 对于不是障碍的每个点 i，连边 ( i -> i', cap = +∞, cost = 0 )
  • 对于有岩石标本的每个点 i，额外连一条边 ( i -> i', cap = 1, cost = 1 )
  • 对于每个点 i 以及其可达的点 j，连边 ( i' -> j, cap = +∞, cost = 0 )
• 答案为最大流量下的最大费用。

#24 骑士共存问题

• 二分图最大点权独立集模板题，首先将棋盘黑白染色，然后按如下方式连边：
  • 对于每个非障碍黑点 i，连边 ( S -> i, cap = 1 )
  • 对于每个非障碍白点 j，连边 ( j -> T, cap = 1 )
  • 对于每个非障碍黑点 i 和其能直达的非障碍白点 j，连边 ( i -> j, cap = +∞ )
• 答案为非障碍点总数减去最小割。

~~ 完结撒花 ~~

附件：[Code]网络流24题