网络流24题

最小割=最大流

最大权闭合图=正权边之和最小割

听说这24个题很好。

开始填坑吧。

1.飞行员配对方案问题　　二分图最大匹配　　　　传送门　　（好像就是个模板呀）

2.太空飞行计划问题　　　最大权闭合图　　　　　传送门

3.最小路径覆盖问题　　　最小不相交路径覆盖　　传送门　　（这个，也不难）

4.魔术球问题　　　　　　最小不相交路径覆盖　　传送门

5.圆桌问题　　　　　　　二分图多重匹配　　　　传送门

6.最长递增子序列问题　　最多不相交路径　　　　传送门

7.试题库问题　　　　　　二分图多重匹配　　　　传送门

8.机器人路径规划问题　　　　　　　　　　　　　不可做

9.方格取数问题　　　　　最大点权独立集　　　　传送门

10.餐巾计划问题　　　　 线性规划网络优化　　　传送门

11.航空路线问题　　　　 最长不相交路径　　　　传送门

12.软件补丁问题　　　　 最短路　　　　　　　　传送门

13.星际转移问题　　　　 网络判定　　　　　　　传送门（分层图思路需要好好体会）

14.孤岛营救问题　　　　 分层图最短路　　　　　传送门（第一发分层图最短路径，挺简单的）

15.汽车加油行驶问题　　 分层图最短路　　　　　传送门

16.

17.运输问题　　　　　　 网络费用流量　　　　　传送门（脑残题）

18.分配问题　　　　　　 二分图最佳匹配　　　　传送门（脑残题）

19.负载平衡问题　　　　 最小代价供求　　　　　传送门

20.深海机器人问题　　　线性规划网络优化　　　传送门（呵呵）

21.

22.

23.火星探险问题　　　　 线性规划网络优化　　　传送门

24.骑士共存问题　　　　 二分图最大独立集　　　传送门

继续继续。

题目链接

上一篇：[luoguP2680] 运输计划（lca + 二分 + 差分）

下一篇：[luoguP2762] 太空飞行计划问题（最大权闭合图—最小割—最大流）

---

二分图 最小点覆盖 最小费用最大流 最大流 最小割 网络流 最大独立集 匈牙利算法 最大权完美匹配