线性规划与网络流24题 解题报告
经过几天努力终于做完了线性规划与网络流24题，同时对网络流和二分图的理解也上升到了一个新的高度。把所有题解发上来供大家参考，还请多多指教。
感谢ShingRay发现本文一个错误，现已修正。
BYVoid原创 线性规划与网络流24题_解题报告Ver 2 (48KB)
另外附上 线性规划与网络流24题 (1.90MB) 感谢王晓东老师给我们提供这么多好题。
几点说明
- 本题解提供所有问题的解析和大部分问题的C++程序源代码，以及个别数据的勘误。
- 本题解只讨论问题的分析和建模，具体的实现参照代码。代码中所有网络最大流算法均用Dinic实现。
- 读者应具备图论、最短路径、网络流的基础知识，并掌握至少一种网络最大流和最小费用最大流的算法。
- 建议读者在阅读题解前先进行充分的思考，确认无法独立解决后再看题解。
- 问题8 机器人路径规划问题 是个经典难题，暂时还未解决，欢迎大家讨论。
- 本题解系个人原创，请勿商业转载，非商业转载请注明来源。
| 问题编号 | 问题名称 | 问题模型 | 转化模型 |
| 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 | 骑士共存问题 | 二分图最大独立集 | 网络最小割 |
上次修改时间 2017-05-22