最小费用最大流问题（Primal-Dual 算法） 题目描述 ： 给定一个带权有向图 \( G = (V, E) \)，每条边 \( e \in E \) 有容量 \( c(e) \geq 0 \) 和单位流量费用 \( w(e) \in \mathbb{R} \)。图中包含源点 \( s \) 和汇点 \( t \)。目标是找到从 \( s \) 到 \( t \) 的最大流 \( f \)，且总费用 \( \sum_ {e} f(e) \cdot w(e) \) 最小。 解题过程 ： 问题建模 ： 最小费用最大流是最大流问题的扩展，要求在保证流量最大的前提下，使总传输费用最小。费用通常代表运输成本或能耗。 关键思想：Primal-Dual 框架 对偶变量（势函数） ：为每个节点 \( u \) 分配势 \( p(u) \)，通过调整势函数将边费用转化为非负值，从而利用 Dijkstra 算法找最短路径。 残量图与费用调整 ：在残量图中，对于边 \( (u, v) \)： 若为原边（容量剩余 \( c_ f(e) > 0 \)），其残量费用为 \( w_ p(u, v) = w(u, v) + p(u) - p(v) \)。 若为反向边（对应反向流量），其残量费用为 \( -w(u, v) + p(u) - p(v) \)。 目标 ：通过势函数使所有残量边费用非负，即 \( w_ p(u, v) \geq 0 \)，从而可在残量图上用 Dijkstra 找最小费用增广路。 算法步骤 ： 步骤 1：初始化 设初始流 \( f(e) = 0 \)，初始势 \( p(u) = 0 \)。 构建残量图 \( G_ f \)，包含原边（剩余容量）和反向边（可减少流量）。 步骤 2：迭代增广 循环执行以下步骤直到无法从 \( s \) 到 \( t \) 找到增广路： 子步骤 2.1：计算最短路径 在残量图中使用 Dijkstra 算法（基于调整后的费用 \( w_ p \)）计算从 \( s \) 到所有节点的最短路径距离 \( d(u) \)。 若 \( d(t) = +\infty \)，说明无增广路，算法终止。 子步骤 2.2：更新势函数 令新势 \( p_ {\text{new}}(u) = p(u) + d(u) \)。此操作保证残量费用保持非负（由 Dijkstra 的最短路径性质保证）。 子步骤 2.3：沿路径增广 从 \( s \) 到 \( t \) 的最短路径上，找到最小剩余容量 \( \Delta = \min\{ c_ f(e) \mid e \in \text{路径} \} \)。 沿该路径推送 \( \Delta \) 单位流量，更新残量图中边的容量（原边容量减少 \( \Delta \)，反向边容量增加 \( \Delta \)）。 正确性说明 ： 势函数更新后，残量费用满足 \( w_ p(u, v) \geq 0 \)，确保 Dijkstra 的适用性。 每次增广的路径是当前残量图中费用最小的路径，保证总费用逐步优化。 算法终止时，流量最大且费用最小（对偶理论保证）。 复杂度分析 ： 每次迭代使用一次 Dijkstra（\( O(|E| + |V|\log |V|) \)）。 最多增广 \( |V| \cdot U \) 次（\( U \) 为最大流量），但实际中常用势函数减少迭代次数，最坏复杂度为 \( O(F \cdot (|E| + |V|\log |V|)) \)（\( F \) 为最大流量值）。 示例演示 （简要）： 假设一个简单图：边 \( (s, a) \) 容量 2、费用 1；边 \( (a, t) \) 容量 2、费用 2。 初始势全零，残量图中 \( w_ p = w \)，Dijkstra 找到路径 \( s \to a \to t \)，费用 3。 推送流量 2 后更新势（例如 \( p(a)=1, p(t)=3 \)），残量边费用调整，无新增广路。最终流量 2，总费用 \( 2 \times 1 + 2 \times 2 = 6 \)。