xxx 最小费用最大流问题（Cycle Canceling 算法） 题目描述 给定一个带权有向图，其中每条边有容量（capacity）和单位流量的费用（cost）。在源点（source）和汇点（sink）之间，求一个最大流，使得总费用最小。该问题称为最小费用最大流（Minimum Cost Maximum Flow, MCMF）问题。 解题过程 1. 问题分析 目标：在达到最大流量的前提下，使总费用最小。 约束：每条边的流量不能超过容量，且除源点和汇点外，其他节点流量守恒。 关键思路：先找到一个可行流（如最大流），然后通过调整流来减少费用，直到无法优化为止。 2. 基本概念 残余网络（Residual Graph） ： 对原图中每条边 \( (u, v) \)，在残余网络中创建两条边： 正向边：剩余容量 = 原容量 - 当前流量，费用 = 原费用。 反向边：剩余容量 = 当前流量，费用 = -原费用（表示可退回流量以减少费用）。 负环（Negative Cycle） ： 在残余网络中，若存在一个环，其边费用之和为负，则沿该环增流可减少总费用。 3. Cycle Canceling 算法步骤 步骤 1：找到初始可行流 使用任意最大流算法（如 Edmonds-Karp 或 Dinic）在原图上求一个最大流，忽略费用。 此时得到一个流量为最大值的流，但费用可能不是最优。 步骤 2：构建残余网络 根据当前流，构建带费用的残余网络（包括正向边和反向边）。 步骤 3：检测负环 在残余网络中，使用 Bellman-Ford 算法检测是否存在负费用环。 Bellman-Ford 算法步骤： 初始化所有节点距离为 0（或使用源点为 0，但负环检测通常无需源点）。 松弛所有边 \( |V|-1 \) 次（\( |V| \) 为节点数）。 再遍历一次所有边，若仍可松弛，说明存在负环。 步骤 4：消除负环 若发现负环，则沿该环增流（即增加环上所有边的流量），增流量为环上边的最小剩余容量。 增流后更新残余网络： 减少正向边的剩余容量，增加反向边的剩余容量。 总费用减少（环的费用为负，流量增加使总费用下降）。 步骤 5：重复检测与消除 重复步骤 3 和 4，直到残余网络中无负环。 此时当前流即为最小费用最大流。 4. 算法正确性 根据线性规划对偶理论，流是最小费用当且仅当残余网络中无负环。 每次消除负环均使费用下降，且费用有下界（有限值），故算法必收敛。 5. 复杂度分析 初始最大流：取决于所用算法（如 Edmonds-Karp 为 \(O(VE^2)\)）。 负环检测：Bellman-Ford 为 \(O(VE)\)。 总复杂度：最坏情况下需消除指数个负环，但实际中常结合其他优化（如 Capacity Scaling）。 6. 实例演示（简略） 假设有图： 边 \( (s, a) \): 容量 5，费用 1； 边 \( (a, t) \): 容量 5，费用 1； 边 \( (s, b) \): 容量 5，费用 2； 边 \( (b, t) \): 容量 5，费用 2。 初始最大流为 10，但若全部经 \( (s, a, t) \) 则费用更低。Cycle Canceling 会通过反向边调整流，使费用最小化。 总结 Cycle Canceling 算法通过不断消除残余网络中的负环，逐步将任意最大流优化为最小费用最大流。其核心在于负环检测与增流操作，确保在达到最大流量的同时总费用最小。