一、费用流的核心概念
费用流（Minimum Cost Maximum Flow, MCMF）是网络流理论的高级延伸，在最大流的基础上，为每条边赋予单位流量费用（即每传输1单位流量需付出的代价），目标是找到流量最大且总费用最小的可行流（最小费用最大流），或流量最大且总费用最大的可行流（最大费用最大流，可通过费用取反转化为最小费用问题）。
1. 形式化定义
对于带权有向图G=(V,E,c,w)（c(u,v)为边(u,v)的容量，w(u,v)为单位流量费用），可行流f需满足：
- 容量限制：0≤f(u,v)≤c(u,v)（正向边）；
- 流量守恒：除源点s和汇点t外，任意节点u的流入流量等于流出流量（∑vf(v,u)=∑vf(u,v)）。
最小费用最大流是在所有可行流中，流量等于最大流且总费用（∑(u,v)f(u,v)⋅w(u,v)）最小的流；最大费用最大流则是总费用最大的流（通常通过将所有边费用取反，求最小费用最大流后再取反结果得到）。
2. 核心术语
- 残量网络：与最大流中的残量网络类似，但需记录反向边的费用（反向边的费用为原边费用的相反数，即w(v,u)=−w(u,v)，用于“反悔”操作，即调整已选路径以降低总费用）；
- 增广路径：残量网络中从s到t的路径，路径上的最小残量（即路径上边的最小剩余容量）决定了可增加的流量；
- 费用增广：沿增广路径增加流量时，总费用的变化为“路径流量×路径总费用”（路径总费用是路径上边的单位费用之和）。
二、费用流的重点知识
1. 核心算法
费用流的求解核心是在最大流的基础上，通过最短路算法寻找费用最小的增广路径，常用算法包括：
（1）EK算法+SPFA（入门级）
核心思想：将最大流的Edmonds-Karp（EK）算法中的BFS（寻找最短增广路径）替换为SPFA（寻找费用最小的增广路径），每次找到一条费用最小的增广路径，增广后更新残量网络，直到无法增广（达到最大流）。
步骤：
- 初始化残量网络（正向边容量为c(u,v)，反向边容量为0）；
- 用SPFA计算残量网络中从s到t的费用最小路径（路径的总单位费用最小）；
- 沿该路径增广（增加路径上的流量，更新正向边和反向边的容量）；
- 累加增广的流量和总费用（流量×路径总费用）；
- 重复步骤2-4，直到SPFA无法找到增广路径（达到最大流）。
优化：
- 当前弧优化：记录每条边的下一次可用起点，避免重复检查已失效的边；
- SLF优化：在SPFA中使用双端队列，将待处理节点插入队首（若其距离小于队首节点），减少队列操作次数。
时间复杂度：O(V⋅E2)（一般图），O(V⋅E)（二分图，因增广路径较短）。
（2）Dinic算法+SPFA（竞赛常用）
核心思想：结合Dinic算法的分层图（按节点到s的最短距离分层）和多路增广（一次DFS寻找多条增广路径），用SPFA代替BFS进行分层，以提高增广效率。
步骤：
- 用SPFA进行分层（计算每个节点的层次，即到s的最小费用距离）；
- 在分层图上进行DFS，寻找所有层次递增的增广路径（即路径上的节点层次依次增加1）；
- 沿找到的增广路径增广，更新残量网络；
- 重复步骤1-3，直到分层图中无法到达t（达到最大流）。
优化：
- 当前弧优化：同EK算法；
- 多路增广：一次DFS寻找多条增广路径，减少SPFA的调用次数。
时间复杂度：O(V2⋅E)（一般图），O(V⋅E)（二分图）。
（3）zkw费用流（高级优化）
核心思想：通过势函数（Vertex Potential）将残量网络中的边费用调整为非负，从而用Dijkstra算法代替SPFA寻找最短路，进一步提高效率。
步骤：
- 初始化势函数（通常为0）；
- 用势函数调整边费用（调整后的费用为w′(u,v)=w(u,v)+potential(u)−potential(v)），使得调整后的费用非负；
- 用Dijkstra算法寻找调整后的残量网络中从s到t的最短路；
- 沿最短路增广，更新残量网络和势函数（势函数更新为当前节点的距离）；
- 重复步骤2-4，直到无法增广。
优势：
- 避免了SPFA的最坏情况（如负环导致的指数级复杂度）；
- 多路增广进一步减少了增广次数，适用于流量大、费用取值范围小的图（如二分图）。
时间复杂度：O(V⋅E⋅logV)（稀疏图），O(V2⋅logV)（稠密图）。
2. 常见模型与技巧
费用流的问题通常需要通过建图技巧将实际问题转化为网络流模型，常见模型包括：
（1）拆点/拆边（处理容量限制）
- 节点容量限制：若节点u的流量不能超过k（如“每个仓库最多存储k单位货物”），则将u拆分为入点uin和出点uout，连接uin到uout的边容量为k，费用为0（原图中的边(u,v)改为(uout,vin)，(v,u)改为(vout,uin)）；
- 边容量限制：若边(u,v)的流量需分阶段计费（如前k单位费用为w1，超过部分为w2），则将边拆分为两条：(u,v)容量为k，费用为w1；(u,v)容量为∞，费用为w2（或使用“增量边”，如容量为1，费用为w2−w1，重复添加k次）。
（2）二分图匹配（最小费用匹配）
- 二分图最大权匹配：将二分图的左部节点连接源点（容量为1，费用为0），右部节点连接汇点（容量为1，费用为0），原图中的边(u,v)容量为1，费用为−w(u,v)（求最小费用最大流，结果为最大权匹配的权值和）；
- 二分图多重匹配：若左部节点u可匹配多个右部节点（容量为ku），则将源点到u的边容量设为ku，其余边同普通二分图匹配。
（3）模拟费用流（贪心优化）
对于大规模图（如n>104），费用流的常规算法（如Dinic+SPFA）可能无法在规定时间内运行，此时需用模拟费用流（通过贪心策略模拟费用流的增广过程）。
核心思想：
- 维护堆（优先队列）记录当前可用的“增广选项”（如未匹配的节点、可反悔的边）；
- 每次选择费用最小的增广选项（如匹配两个节点的费用最小），更新堆中的选项（如添加反悔后的新选项）；
- 重复直到达到最大流。
典型应用：
- 老鼠进洞问题（数轴上老鼠和洞的匹配，求最小总距离）；
- 任务分配问题（员工与任务的匹配，求最小总愤怒值）。
三、费用流的学习方法
1. 基础铺垫：掌握最大流与最短路
费用流的学习依赖最大流（如Dinic算法）和最短路（如SPFA、Dijkstra）的基础，需先掌握：
- 最大流的定义、残量网络、增广路径；
- 最短路算法的原理与实现（尤其是SPFA和Dijkstra）。
2. 核心技能：算法模板与优化
- 第一步：背诵费用流的模板（如EK+SPFA、Dinic+SPFA），理解每一步的作用（如SPFA寻找费用最小路径、增广时更新残量网络）；
- 第二步：用模板解决简单题（如洛谷P3381“最小费用最大流”模板题），熟悉输入输出格式；
- 第三步：学习优化技巧（如当前弧优化、势函数优化），对比优化前后的效率差异（如用zkw费用流解决洛谷P3381，观察运行时间变化）。
3. 专项练习：从经典题到变形题
- 入门题：
- 洛谷P3381（“最小费用最大流”模板题，练习EK+SPFA或Dinic+SPFA）；
- POJ 2195（“Going Home”，二分图最小费用匹配，练习拆点与SPFA）。
- 进阶题：
- 洛谷P2517（“订货”，最小费用最大流，练习处理节点容量限制与时间维度）；
- POJ 3680（“Intervals”，区间覆盖的最小费用，练习拆边与SPFA）。
- 难题：
- 洛谷P3358（“最长k可重区间集问题”，最小费用最大流，练习处理区间重叠与k限制）；
- CF1082F（“Speed Dial”，模拟费用流，练习贪心策略与堆的使用）。
4. 参考资料与工具
- 书籍与博客：《图论导引》（网络流章节）、《算法竞赛进阶指南》（费用流部分）、Amber论文《最小费用流模型在信息学竞赛中的应用》；
- 在线平台：洛谷（费用流专题）、Codeforces（Div.1+ 费用流题）、OI-wiki（“费用流”专题）；
- 工具：NetworkX（Python图论库，支持费用流计算）、Dinic模板（竞赛常用）、zkw费用流代码（高级优化）。
四、总结
费用流的核心是在最大流的基础上，通过最短路算法寻找费用最小的增广路径，其关键是建图技巧（将实际问题转化为网络流模型）和算法优化（如当前弧优化、势函数优化）。学习时需从基础概念入手，掌握算法模板，通过专项练习提升建模能力（如拆点、二分答案），最终能熟练解决各类费用流问题。推荐的练习顺序是：模板题→经典模型题→复杂变形题→实际问题，逐步实现“看到问题就能想到用费用流建模”的目标。