2026 年省选专题系列二：网络流建模技巧。
网络流基础
- 最大流 = 最小割
- Dinic 算法 O(n²m)
- ISAP 算法
- HLPP 算法
经典建模技巧
1. 二分图匹配：左右部点，边容量 1，求最大匹配。
2. 最小路径覆盖：拆点，DAG 上的最小路径覆盖 = 点数 - 最大匹配。
3. 最大权闭合子图：正权源点连，负权汇点连，求最小割。
4. 二元关系建模：处理两个变量的选择问题。
经典题型
- 任务分配问题
- 方格取数
- 最大权闭合子图
- 平面图最小割
学习建议
- 先掌握 Dinic 模板
- 再学建模技巧
- 多做建模类题目
省选一对一辅导：151 6522 2880