xxx 最小费用最大流问题（Successive Shortest Path with Potentials 算法） 问题描述 给定一个带权有向图G=(V,E)，其中每条边e∈E有一个容量c(e)≥0和一个费用w(e)∈R。图中有一个源点s和一个汇点t。最小费用最大流问题要求从s到t输送尽可能多的流，同时使总费用最小。 解题过程 1. 问题分析 我们需要同时优化两个目标：流量最大化和费用最小化 这可以看作是在最大流的基础上寻找费用最小的方案 算法需要维护两个关键性质：流量可行性和费用最优性 2. 残量网络构建 首先构建残量网络G_ f = (V, E_ f)： 对于原图中的每条边(u,v)∈E，容量为c，费用为w 在残量网络中创建正向边(u,v)，剩余容量为c-f，费用为w 创建反向边(v,u)，剩余容量为f，费用为-w 这样设计的目的是允许"撤销"已发送的流 3. 势函数引入 势函数h: V→R的作用： 重新定义边的费用为w'(u,v) = w(u,v) + h(u) - h(v) 关键性质：在势函数变换下，任意环的费用总和保持不变 这保证了费用最优性的等价性 4. 算法核心步骤 步骤1：初始化 初始流f=0 初始势函数h(v)=0，对所有v∈V 计算从源点s到所有点的最短路径距离d(v) 步骤2：更新势函数 设置h(v) = h(v) + d(v)，对所有v∈V 这确保了变换后的费用w'都是非负的 步骤3：寻找增广路径 在残量网络中使用Dijkstra算法： 使用变换后的费用w'(u,v) = w(u,v) + h(u) - h(v) 由于w'≥0，可以使用高效的Dijkstra算法 找到从s到t的最短路径P 步骤4：沿路径增广 计算路径P上的最小剩余容量：δ = min{(u,v)∈P} r(u,v) 沿路径P推送δ单位的流 更新残量网络中的容量： 对正向边：剩余容量减少δ 对反向边：剩余容量增加δ 步骤5：重复执行 重复步骤2-4，直到无法找到从s到t的路径 此时得到的流就是最小费用最大流 5. 正确性保证 势函数保持变换后费用非负，使得Dijkstra算法可用 每次迭代都沿着当前费用最小的路径增广 算法终止时，既达到最大流，又保证费用最小 6. 复杂度分析 每次Dijkstra：O(|E| + |V|log|V|) 最多增广|f* |次，其中f* 是最大流值 总复杂度：O(|f* |(|E| + |V|log|V|)) 这个算法通过势函数巧妙地处理了负费用边的问题，使得可以使用高效的Dijkstra算法，是解决最小费用最大流问题的经典方法。