Network Flow
Implementation
Dinic最大流
各种剪枝
Dinic费用流
队列优化的bellman-ford, 实现时需要注意入队标记!
HLPP最大流
- 用优先队列会多\(\log\). (\(O(n^2\sqrt m\log n)\))
- 直接使用队列是\(O(n^3)\)的.
- gap优化
- bfs确定初始高度.
建图
最大流
按照定义建图
最小割
- 对于一条路径上的所有边, 是选择关系.
- 通过连inf边, 实现各种约束条件.
二分图匹配
在两个集合之间连接有向边即可.
最大权闭合子图
提前计算所有正权点的贡献.
运用最小割模型, source向正权点连 cap=权值 的边, 表示不选的代价; 负权点向sink连 cap=|权值| 的边, 表示选择的代价. 对原图中的边对应建一条inf边.
发现合法的子图一定是一个割.
最小路径覆盖
转化为二分图匹配: 每个点入度, 出度最多为1, 并且每连一条边, 入度, 出度均+1. 将每个点拆成入点和出点跑二分图匹配.
网络流24题
#6000. 「网络流 24 题」搭配飞行员
二分图最大匹配.
#6001. 「网络流 24 题」太空飞行计划
转化为最大权闭合子图
#6002. 「网络流 24 题」最小路径覆盖
最小路径覆盖
#6003. 「网络流 24 题」魔术球
增量网络流, 跑最小路径覆盖.
#6004. 「网络流 24 题」圆桌聚餐
最大流建图.
#6005. 「网络流 24 题」最长递增子序列
WA'ed QAQ
#6006. 「网络流 24 题」试题库
最大流建图
#6007. 「网络流 24 题」方格取数
最小割建图.(多变量选择)
#6008. 「网络流 24 题」餐巾计划
费用流建图
#6009. 「网络流 24 题」软件补丁
不是网络流...
#6010. 「网络流 24 题」数字梯形
费用流建图
#6011. 「网络流 24 题」运输问题
费用流建图
#6012. 「网络流 24 题」分配问题
同 #6011
#6013. 「网络流 24 题」负载平衡
简单建图
#6014. 「网络流 24 题」最长 k 可重区间集
考虑在数轴上建立网络流, 额外加入每一条长度为0的线段, 这样就变成一定覆盖k次.
#6015. 「网络流 24 题」星际转移
对时间拆点
#6121. 「网络流 24 题」孤岛营救问题
直接DP
#6122. 「网络流 24 题」航空路线问题
费用流+拆点.