分类
Level9

最大流

一、最大流的核心概念

最大流（Maximum Flow）是网络流理论中的基本问题，旨在寻找从源点（Source, 记为s）到汇点（Sink, 记为t）的最大可能流量，满足以下约束：

  1. 容量限制：每条边(u,v)的流量f(u,v)不超过其容量c(u,v)（即0≤f(u,v)≤c(u,v)）；
  2. 流量守恒：除源点和汇点外，任意中间节点u的流入流量等于流出流量（即∑v∈V​f(v,u)=∑v∈V​f(u,v)）。

关键术语：

  • 残量网络（Residual Network）：反映当前流量分配下剩余容量的辅助网络，记为Gf​。对于边(u,v)，残量为cf​(u,v)=c(u,v)−f(u,v)，反向边(v,u)的残量为f(u,v)（用于“回流”流量）；
  • 增广路径（Augmenting Path）：残量网络中从s到t的简单路径，路径上的最小残量决定了可增加的流量；
  • 最大流最小割定理（Max-Flow Min-Cut Theorem）：任意网络的最大流流量等于其最小割容量。其中，割（Cut）是将顶点集划分为S（含s）和T=V∖S（含t）的分割，割容量为∑u∈S,v∈T​c(u,v)。

二、最大流的重点知识

1. 核心算法

最大流算法主要分为两类：增广路径方法（如Ford-Fulkerson、Edmonds-Karp、Dinic）和预推进算法（如Push-Relabel）。其中，Dinic算法是竞赛中最常用的高效算法，以下是重点介绍：

（1）Dinic算法（分层图+阻塞流）

核心思想：通过分层图（Level Graph）和阻塞流（Blocking Flow）优化增广路径的寻找，避免重复遍历。

步骤：

  1. BFS分层：从s出发进行BFS，记录每个节点的层次（即s到该节点的最短距离），构建分层图；
  2. DFS找阻塞流：在分层图上进行DFS，寻找从s到t的增广路径集合（阻塞流是指无法再找到增广路径的流）；
  3. 更新残量网络：沿阻塞流更新残量，累加流量；
  4. 重复：直到分层图中无法到达t（即没有增广路径）。

优化技巧：

  • 层次剪枝：只允许从第k层节点访问第k+1层节点，减少无效遍历；
  • 当前弧优化：记录每条边的下一次可用起点，避免重复检查已失效的边；
  • 多路增广：一次DFS寻找多条增广路径，提高效率。

时间复杂度：O(E⋅V2)（一般图），O(E⋅V​)（单位容量图）。

（2）Edmonds-Karp算法（BFS增广）

核心思想：用BFS寻找最短增广路径（边数最少），避免DFS可能出现的“绕远路”问题。

时间复杂度：O(V⋅E2)，适用于小规模图。

（3）Push-Relabel算法（预推进）

核心思想：通过“压入”（Push）操作将流量从高位节点推到低位节点，通过“重标记”（Relabel）操作调整节点高度，直到无法压入。

特点：无需寻找增广路径，适用于大规模图，时间复杂度为O(V2⋅E)（Highest Label Preflow Push变种）。

2. 常见模型与技巧

  • 二分图最大匹配：将二分图左右部节点分别连接源汇点，边容量设为1，最大流即为最大匹配数；
  • 拆点/拆边：处理节点容量限制（如每个节点最多处理k个流量），将节点拆分为入点和出点，中间连容量为k的边；
  • 二分答案：对于“最大化最小值”问题（如“最优灌溉”），二分可能的答案，将符合条件的边加入网络，判断是否满足满流；
  • 多源多汇问题：添加超级源点（连接所有源点，容量无穷大）和超级汇点（连接所有汇点，容量无穷大），转化为单源单汇问题。

三、最大流的学习方法

1. 夯实基础：理解概念与定理

  • 必学内容：最大流的定义、容量限制与流量守恒、残量网络、增广路径、最大流最小割定理；
  • 参考资源：《图论导引》（网络流章节）、OI-wiki“网络流”专题（https://oi-wiki.org/graph/flow/）。

2. 掌握核心算法：从模板到优化

  • 第一步：背诵Dinic算法的模板（包括分层图、DFS阻塞流、当前弧优化），理解每一步的作用；
  • 第二步：用模板解决简单题（如洛谷P3376“网络最大流”、POJ 1273“Drainage Ditches”），熟悉输入输出格式；
  • 第三步：学习优化技巧（如当前弧优化、多路增广），对比优化前后的效率差异。

3. 专项练习：从经典题到变形题

  • 入门题：洛谷P3376（模板题）、POJ 1459（Power Network）；
  • 进阶题：POJ 2112（Optimal Milking，二分答案+最大流）、POJ 1149（PIGS，拆点+最大流）；
  • 难题：HDU 3605（Escape，状态压缩+最大流）、HDU 3416（Marriage Match IV，最短路+最大流）。

4. 实战应用：参与竞赛与项目

  • 竞赛：参加ICPC、CCPC等算法竞赛，接触更复杂的最大流问题（如多商品流、带费用的流）；
  • 项目：尝试用最大流解决实际问题（如网络带宽分配、图像分割中的图切割），参考PyMaxflow库（https://github.com/pmneila/PyMaxflow）。

四、总结

最大流的核心是寻找增广路径和优化残量网络，其中Dinic算法是竞赛中最实用的工具。学习时需从基础概念入手，掌握算法模板，通过专项练习提升建模能力（如拆点、二分答案），最终能熟练解决各类最大流问题。推荐的练习顺序是：模板题→经典题→变形题→实际问题。