题解咕了。
| 序号 | 名称 | 标签 | 状态 |
|---|---|---|---|
| 1 | 飞行员配对方案问题 | 二分图最大匹配 -> 最大流 | \(\surd\) |
| 2 | 太空飞行计划问题 | 最大权闭合子图 -> 最小割 | \(\surd\) |
| 3 | 最小路径覆盖问题 | DAG最小路径覆盖 -> 二分图最大匹配 -> 最大流 | \(\surd\) |
| 4 | 魔术球问题 | DAG最小路径覆盖 -> 二分图最大匹配 -> 最大流 | \(\surd\) |
| 5 | 圆桌问题 | 二分图多重匹配 -> 最大流 | \(\surd\) |
| 6 | 最长不下降子序列问题 | 最多不相交路径 -> 最大流 | \(\surd\) |
| 7 | 试题库问题 | 二分图多重匹配 -> 最大流 | \(\surd\) |
| 8 | 机器人路径规划问题 | （未解决） | \(\times\) |
| 9 | 方格取数问题 | 二分图点权最大独立集 -> 最小点覆盖 -> 最小割 | \(\surd\) |
| 10 | 餐巾计划问题 | 线性规划网络优化 -> 费用流 | \(\surd\) |
| 11 | 航空路线问题 | 最长不相交路径 -> 费用流 | \(\surd\) |
| 12 | 软件补丁问题 | 最小转移代价 -> 最短路 | \(\surd\) |
| 13 | 星际转移问题 | 最大流 | \(\surd\) |
| 14 | 孤岛营救问题 | BFS | \(\surd\) |
| 15 | 汽车加油行驶问题 | 分层图最短路(SPFA) -> 费用流 | \(\surd\) |
| 16 | 数字梯形问题 | 最大权不相交路径 -> 费用流 | \(\surd\) |
| 17 | 运输问题 | 费用流 | \(\surd\) |
| 18 | 分配问题 | 二分图最佳匹配 -> 费用流 | \(\surd\) |
| 19 | 负载平衡问题 | 最小代价供求 -> 费用流 | \(\surd\) |
| 20 | 深海机器人问题 | 线性规划网络优化 -> 最大费用最大流 | \(\surd\) |
| 21 | 最长k可重区间集问题 | 最大权不相交路径 -> 最大费用最大流 | \(\surd\) |
| 22 | 最长k可重线段集问题 | ||
| 23 | 火星探险问题 | 线性规划网络优化 -> 最大费用最大流 | \(\surd\) |
| 24 | 骑士共存问题 | 二分图最大独立集 -> 最小点覆盖 -> 最小割 | \(\surd\) |
原文：https://www.cnblogs.com/newbielyx/p/12208472.html