xxx 最小费用最大流问题（Successive Shortest Path算法） 题目描述 给定一个带权有向图G=(V, E)，其中每条边e=(u, v)有一个容量c(e)≥0和一个费用w(e)。图中包含一个源点s和一个汇点t。最小费用最大流问题要求我们找到从s到t的一个流方案，使得总流量达到最大值，并且在所有最大流方案中，该方案的总费用最小。总费用定义为流经每条边的流量乘以其单位费用的总和。 解题过程 1. 问题建模与关键概念 流函数f : 满足容量限制（0≤f(e)≤c(e)）和流量守恒（除s和t外，流入等于流出）。 目标 : 最大化流量值|f|，同时最小化总费用∑(f(e)·w(e))。 核心思想 : 在寻找增广路径时，优先选择单位费用最小的路径，逐步增加流量直至最大流。 2. 残余网络与负费用环 构建残余图G_ f： 对于原边e=(u, v)，若f(e) <c(e)，添加正向边（容量c(e)-f(e)，费用w(e)）。 对于反向边e'=(v, u)，若f(e)>0，添加反向边（容量f(e)，费用-w(e)）。 关键性质 : 若残余图中存在负费用环，则可通过调整环上的流量降低总费用而不改变总流量。 3. 算法步骤（Successive Shortest Path） 步骤1: 初始化 设初始流f=0，残余图G_ f与原图相同。 使用Bellman-Ford算法计算从s到所有顶点的最短路径距离d(v)（以费用为边权），检测是否存在负环。若存在，问题无界（通常假设无负环）。 步骤2: 迭代增广 While 在残余图G_ f中存在从s到t的路径： 使用最短路径算法（如Dijkstra）在G_ f中计算从s到所有顶点的最短路径，路径权重为边费用。 注意 ：需保证边权非负。通过势函数h(v)=d(v)调整边权：新权值w'(u, v)=w(u, v)+h(u)-h(v)≥0。 若 找到一条s到t的最短路径P： 计算路径P的残余容量Δ=min_ {e∈P} (残余容量)。 沿P增广流量Δ，更新流f：对P上的正向边增加Δ，反向边减少Δ。 更新残余图G_ f的容量。 否则 ：退出循环（已达到最大流）。 步骤3: 输出结果 当前流f即为最小费用最大流，总费用为∑f(e)·w(e)。 4. 势函数与边权调整 目的：使Dijkstra算法适用于非负权图。 定义势函数h(v)为上一轮Bellman-Ford计算的距离d(v)。 调整边权：w'(u, v)=w(u, v)+h(u)-h(v)。 性质 ：调整后边权非负，且路径相对长度不变。 5. 复杂度分析 使用势函数后，每次增广使用Dijkstra算法，时间复杂度O(|E|log|V|)。 最多增广|f|次（最大流值），总复杂度O(|f|·|E|log|V|)。 举例说明 假设简单图：s→a（容量2，费用1）、a→t（容量2，费用2）、s→t（容量1，费用4）。 初始流为0，残余图与原图相同。 第一轮增广：选择最短路径s→a→t（费用1+2=3），增广流量2，更新流和残余图。 第二轮增广：仅剩路径s→t（费用4），增广流量1，达到最大流3。 总费用=2×3 + 1×4=10，为最小费用。 通过逐步选择最小费用路径增广，最终得到流量最大且总费用最小的解。