回过头来重新做一遍网络流24题
| 飞行员配对问题 | 最大流 |
| 太空飞行计划问题 | 最小割,S向每个计划实验连pi的边,每个实验向需要的仪器连无穷的边,每个仪器向T连ci的边,这样$\sum_{i=1}^{m}p_i-maxflow$ 就是答案 |
| 最小路径覆盖问题 | 答案等于n-每条路径上的边数和,做一遍二分图匹配就行 |
| 魔术球问题 | 枚举答案,转化为最小路径覆盖 |
| 圆桌问题 | 最大流 |
| 最长递增子序列问题 |
先求出以i点结束的最长上升子序列的长度f[i],从S向f[i]=1点连边,从f[i]=s的点向T连边,从f[j]+1=f[i]&j<i&a[j]<=a[i]的j点向i点连边,跑最大流. |
| 试题库问题 | 最大流 |
| 机器人路径规划 | 暂未解决 |
| 方格取数问题 | 最小割,黑白染色,黑的放左边,白的放右边,相邻方格连边 |
| 餐巾计划问题 | 费用流,拆点. |
| 航空路线问题 | 最大流,拆点限制每个城市只走一次 |
| 软件补丁问题 | 二进制表示bug状态,转为为最短路 |
| 星际转移问题 | 枚举答案t,将每个空间站拆分成t个点 |
| 孤岛营救问题 |
二进制表示钥匙状态,最短路 |
| 汽车加油行驶问题 | 最短路.拆点,(i,j)表示在i点油量为j的状态,根据题意设置边和距离 |
| 数字梯形问题 | 最大费用最大流,根据规则拆点以及设置边的容量 |
| 运输问题 | 费用流 |
| 分配问题 | 最大和最小费用流 |
| 负载平衡问题 | S向大于平均值的仓库连边,小于平均值的仓库向T连边,相邻的仓库连边 |
| 深海机器人问题 | 最大费用最大流 |
| 最长 k 可重区间集问题1 | 离散化所有端点,最大费用最大流 |
| 最长 k 可重线段集问题2 | 同1差不多,改下费用就行了 |
| 火星探险问题 | 最大费用流拆点,i.a向i.b分别连费用１容量１的边和费用０容量无穷的边 |
| 骑士共存问题 | 黑白染色，二分图最大独立集 |
原文：http://www.cnblogs.com/hiaatcnd/p/5389196.html