线性规划与网络流24题 解题报告

经过几天努力终于做完了线性规划与网络流24题,同时对网络流和二分图的理解也上升到了一个新的高度。把所有题解发上来供大家参考,还请多多指教。

感谢ShingRay发现本文一个错误,现已修正。

BYVoid原创 线性规划与网络流24题_解题报告Ver 2 (48KB)

另外附上 线性规划与网络流24题 (1.90MB) 感谢王晓东老师给我们提供这么多好题。

几点说明

  1. 本题解提供所有问题的解析和大部分问题的C++程序源代码,以及个别数据的勘误。
  2. 本题解只讨论问题的分析和建模,具体的实现参照代码。代码中所有网络最大流算法均用Dinic实现。
  3. 读者应具备图论、最短路径、网络流的基础知识,并掌握至少一种网络最大流和最小费用最大流的算法。
  4. 建议读者在阅读题解前先进行充分的思考,确认无法独立解决后再看题解。
  5. 问题8 机器人路径规划问题 是个经典难题,暂时还未解决,欢迎大家讨论。
  6. 本题解系个人原创,请勿商业转载,非商业转载请注明来源。
问题一览

问题编号 问题名称 问题模型 转化模型
1 飞行员配对方案问题 二分图最大匹配 网络最大流
2 太空飞行计划问题 最大权闭合图 网络最小割
3 最小路径覆盖问题 有向无环图最小路径覆盖 网络最大流
4 魔术球问题 有向无环图最小路径覆盖 网络最大流
5 圆桌问题 二分图多重匹配 网络最大流
6 最长递增子序列问题 最多不相交路径 网络最大流
7 试题库问题 二分图多重匹配 网络最大流
8 机器人路径规划问题 (未解决) 最小费用最大流
9 方格取数问题 二分图点权最大独立集 网络最小割
10 餐巾计划问题 线性规划网络优化 最小费用最大流
11 航空路线问题 最长不相交路径 最小费用最大流
12 软件补丁问题 最小转移代价 最短路径
13 星际转移问题 网络判定 网络最大流
14 孤岛营救问题 分层图最短路径 最短路径
15 汽车加油行驶问题 分层图最短路径 最短路径
16 数字梯形问题 最大权不相交路径 最小费用最大流
17 运输问题 网络费用流量 最小费用最大流
18 分配问题 二分图最佳匹配 最小费用最大流
19 负载平衡问题 最小代价供求 最小费用最大流
20 深海机器人问题 线性规划网络优化 最小费用最大流
21 最长k可重区间集问题 最大权不相交路径 最小费用最大流
22 最长k可重线段集问题 最大权不相交路径 最小费用最大流
23 火星探险问题 线性规划网络优化 最小费用最大流
24 骑士共存问题 二分图最大独立集 网络最小割

相关日志