网络流 24 题集锦及解析

  • 2018-05-01
  • 0
  • 4

网络流 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 = +∞ )
  • 答案为非障碍点总数减去最小割

~~ 完结撒花 ~~

附件:[Code]网络流24题

评论

  • Insania回复

    催更!

  • memset0回复

    据不一定可靠消息称“机器人路径规划问题”有一种O(n^5)的方法。

  • memset0回复

    以及前两天博客怎么咕了?以及膜拜大佬。。。



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai