xxx 最小费用最大流问题（Primal-Dual 算法） 题目描述 给定一个带权有向图，其中每条边有两个属性：容量（capacity）和单位流量费用（cost）。同时指定源点（source）和汇点（sink）。目标是在满足容量约束的前提下，从源点向汇点输送尽可能多的流量，并使得总费用（流量 × 单位费用之和）最小。 解题过程 问题建模 最小费用最大流问题可视为最大流问题的扩展，需在最大流的基础上优化费用。核心思想是通过反复寻找当前残量网络中从源点到汇点的最短路径（按费用计算），并沿该路径推送流量，逐步逼近最优解。 残量网络构建 对原图中每条边 \( (u, v) \)，在残量网络中创建两条边： 正向边：容量为原边容量，费用为原费用 \( c(u,v) \)； 反向边：容量为0，费用为 \( -c(u,v) \)（用于流量回退时费用抵消）。 初始时所有边流量为0，残量网络与原图一致。 Primal-Dual 算法框架 步骤1 ：初始化流量 \( f = 0 \)，总费用 \( \text{cost} = 0 \)。 步骤2 ：在残量网络中，使用 Bellman-Ford 算法（或SPFA）计算从源点出发到所有顶点的最短路径（按费用），得到势能函数 \( h(v) \)。势能用于调整边费用，确保非负性。 步骤3 ：若汇点不可达，说明已达到最大流，算法终止。 步骤4 ：根据势能 \( h \) 调整边费用：对残量网络中每条边 \( (u,v) \)，新费用定义为 \( c_ h(u,v) = c(u,v) + h(u) - h(v) \)。此操作保证调整后费用非负，且最短路径结构不变。 步骤5 ：在调整后的网络上使用 Dijkstra 算法找从源点到汇点的最短路径（按非负费用）。 步骤6 ：沿找到的最短路径推送尽可能多的流量（路径上最小残存容量）。更新流量 \( f \) 和总费用 \( \text{cost} \)。 步骤7 ：更新势能：\( h_ {\text{new}}(v) = h_ {\text{old}}(v) + d(v) \)，其中 \( d(v) \) 是步骤5中Dijkstra计算的最短距离。 步骤8 ：重复步骤3–7直至无法增广。 关键点说明 势能函数的作用 ：通过势能调整边费用，使得Dijkstra可替代Bellman-Ford，将每次增广的时间复杂度从 \( O(VE) \) 降为 \( O(E \log V) \)。 费用非负保证 ：调整后费用满足 \( c_ h(u,v) \geq 0 \)，这是Dijkstra适用的前提。 终止条件 ：当残量网络中源点到汇点不再连通时，当前流即为最小费用最大流。 复杂度分析 每次增广使用一次Dijkstra，时间复杂度 \( O(E \log V) \)。 最多增广 \( O(f_ {\max}) \) 次（\( f_ {\max} \) 为最大流值），总复杂度 \( O(f_ {\max} \cdot E \log V) \)。 若边费用均为整数，算法能保证正确性；对于浮点数费用需注意精度问题。 示例 考虑一个简单网络：源点 \( s \)，汇点 \( t \)，中间节点 \( a, b \)。边集包括 \( (s,a) \)（容量2，费用1）、\( (s,b) \)（容量3，费用3）、\( (a,t) \)（容量2，费用2）、\( (b,t) \)（容量2，费用1）、\( (a,b) \)（容量1，费用1）。 算法会优先选择费用低的路径（如 \( s \to a \to t \)）增广，再通过调整势能后选择其他路径（如 \( s \to b \to t \) 或 \( s \to a \to b \to t \)）优化总费用，最终得到最大流4，最小费用11。