「网络流24题」总结及图示

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

二分图

• 最大匹配: 匈牙利/最大流
• 带权匹配: KM/费用流
• 最小点覆盖: =最大匹配
• 最小边覆盖: =总结点数-最大匹配
• 最大独立集: =总结点数-最大匹配

网络流

• 建立超级源点,超级汇点
• 点存在限制,拆成出入点,将出入点之间的边看做点,限制流量
• 建图考虑左右二部
• 超级源点向源点的边可以限制总流量
• 无源汇有容量下界:s-下界->v u-下界->t u-上界减下界->v,当满流时存在可行流
• 最小割中赋流量为inf则一定不会割去
• 一些求最大问题,可以用sum-最小割
• 最大权闭合图: 建图,最小割,仍和s相连的为最大权闭合图,权值和为sum-最小割

24题

1. 直接建二分图,最大流求最大匹配
2. 最大权闭合图,建边,实验和仪器之间保证不切割容量为inf,跑最小割,找与s相连的实验和仪器
3. 最大独立集,总结点数-最大流
4. 贪心
5. 二分图多重匹配,s->左点集和右点集->t之间的边容量不为1(即可以选多次)
6. 动态规划+按照动态规划的dp数组的意义建边求最大流
7. 二分图多重匹配,类型-题目数->汇点,保证可选多个,存在满流则存在答案沿满流输出
8. $IDA*$爆搜,但洛谷数据应该有问题
9. 抽象出两个点集,求最大独立集
10. 按照题目说明建图,跑费用流
11. 按照题目说明建图,跑费用流
12. 将错误状态进行压缩,然后跑最短路
13. 根据时间逐层建图,直到跑出可行流
14. 将拥有钥匙进行压缩,跑最短路
15. 建出分层图,跑最短路或者费用流
16. 对三个规则分别建图,跑费用流
17. 纯费用流
18. 二分图最佳匹配,使用费用流
19. 费用流,注意环形
20. 按照题目要求建图,跑费用流
21. 离散化,将区间转化为边,费用流
22. 转化问题,变成21题,注意端点处理和垂直于x轴的线段
23. 按照题目要求建图,跑费用流,方案dfs
24. 将图上所有格点转化为两个点集,建二分图,求最大独立集

图示

更新中