网络流 24 题集锦及解析
网络流 24 题题目列表
题目编号 | 题目名称 | 对应模型 |
---|---|---|
#01 | 飞行员配对方案问题 | 二分图最大匹配 |
#02 | 太空飞行计划问题 | 最大权闭合子图 |
#03 | 最小路径覆盖问题 | 二分图最大匹配 |
#04 | 魔术球问题 | 二分图最大匹配 |
#05 | 圆桌问题 | 二分图多重匹配 |
#06 | 最长不下降子序列问题 | 网络最大流 |
#07 | 试题库问题 | 二分图多重匹配 |
#08 | 机器人路径规划问题 | (不可做题,或可用随机化方法) |
#09 | 方格取数问题 | 二分图最大点权独立集 |
#10 | 餐巾计划问题 | 最小费用最大流 |
#11 | 航空路线问题 | 最大费用最大流 |
#12 | 软件补丁问题 | 最短路 |
#13 | 星际转移问题 | 网络最大流 |
#14 | 孤岛营救问题 | 最短路 |
#15 | 汽车加油行驶问题 | 最短路 |
#16 | 数字梯形问题 | 最大费用最大流 |
#17 | 运输问题 | 最小/大费用最大流 |
#18 | 分配问题 | 二分图最大完美匹配 |
#19 | 负载平衡问题 | 最小费用最大流 |
#20 | 深海机器人问题 | 最小费用最大流 |
#21 | 最长k可重区间集问题 | 最大费用最大流 |
#22 | 最长k可重线段集问题 | 最大费用最大流 |
#23 | 火星探险问题 | 最大费用最大流 |
#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(n9) 的缓慢的网络流算法,以及一种 O(n6) 的动态规划算法,但均不能通过此题。
- 可用随机化算法,牺牲正确性以获得高分,或可通过此题。
#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 坐标中较小值为 x1,较大值为 x2,连边 ( x1' -> x2, 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 = +∞ )
- 答案为非障碍点总数减去最小割。
Insania
催更!
willem
yx巨爷我错了[可怜][可怜]
memset0
据不一定可靠消息称“机器人路径规划问题”有一种O(n^5)的方法。
memset0
以及前两天博客怎么咕了?以及膜拜大佬。。。