xxx 最小费用最大流问题（Successive Shortest Path算法）

题目描述
在一个有向图中，每条边有一个容量（表示能通过的最大流量）和一个费用（表示每单位流量通过该边所需的成本）。给定一个源点s和一个汇点t，我们需要找到从s到t的最大流，并且在所有可能的最大流中，总费用最小的那个流。这就是最小费用最大流问题。

解题过程

1. 问题理解与初始设置

   • 目标：在满足容量约束的前提下，发送尽可能多的流量从s到t，同时使总费用最小。
   • 初始流：通常从零流开始（即所有边上的流量为0）。
   • 关键思想：在残余网络中寻找从s到t的最短路径（按费用计算），并沿该路径推送尽可能多的流量。重复此过程直到无法再增加流量。

2. 构建残余图

   • 对于原图中的每条边(u, v)，容量为c，费用为w，当前流量为f：
     • 正向边：残余容量为 c - f，费用为 w。
     • 反向边：残余容量为 f，费用为 -w（允许撤销流量，并退还费用）。
   • 残余图包含了所有残余容量大于0的边。

3. 使用Successive Shortest Path算法

   • 步骤1：初始化流量f为0，总费用cost为0。
   • 步骤2：在当前的残余图中，使用一个能够处理负权边的最短路径算法（如Bellman-Ford或SPFA）找到从源点s到所有其他顶点的最短路径（按费用计算）。这一步确保了即使在有负费用边（反向边）的情况下，也能正确计算最短路径。
   • 步骤3：如果从s到t不存在路径（即距离为无穷大），算法终止。当前流f即为最大流，cost即为最小总费用。
   • 步骤4：否则，在找到的s-t最短路径上，找出路径上所有边的最小残余容量（即该路径能承载的最大流量增量Δf）。
   • 步骤5：沿这条路径推送Δf的流量：
     • 对于路径上的每条正向边，增加流量Δf。
     • 对于路径上的每条反向边（如果存在），减少流量Δf（相当于撤销原有流量）。
     • 更新总费用：cost += (路径的费用长度) × Δf。
   • 步骤6：更新残余图（调整相关边的残余容量），然后返回步骤2。

4. 算法正确性保证

   • 该算法正确性的关键在于每次迭代都沿着当前费用最小的路径增广流量。通过残余网络中反向边的负费用，算法能够“撤销”之前费用较高的流量分配，从而逐步逼近最小费用流。
   • 为了保证能处理负权边，初始的最短路径计算需要使用Bellman-Ford等算法。一旦初始距离计算完成，后续的残余图可以通过重新权重技术（如Johnson算法中的思想）避免负权圈，从而可以使用更快的Dijkstra算法进行后续最短路径计算，提升效率。

5. 复杂度分析

   • 最坏情况下，算法需要进行O(F)次增广（F是最大流值）。
   • 每次增广需要一次最短路径计算，若使用Bellman-Ford，则为O(VE)。因此总复杂度为O(F * V * E)。
   • 通过引入势函数（Potential Function）并改用Dijkstra算法，可以将每次最短路径计算优化到O(E log V)，总复杂度降为O(F * E log V)。

通过以上步骤，Successive Shortest Path算法能够有效地找到有向图中的最小费用最大流。