网络流是省选进阶的核心算法。

网络流的基本概念

  • 源点 S：起点
  • 汇点 T：终点
  • 边权：容量
  • 流量：实际流过的量

最大流问题

从源点到汇点，最大能流多少流量。

最大流算法

  • Ford-Fulkerson
  • Edmonds-Karp
  • Dinic（最常用）
  • ISAP
  • HLPP

最小割定理

最大流 = 最小割

经典应用

  • 二分图匹配
  • 任务分配
  • 网络设计
  • 最小路径覆盖

省选一对一辅导：151 6522 2880