基于线性规划的图最小费用流问题的成本缩放算法求解示例 我将为您讲解最小费用流问题中的成本缩放算法。这是一个结合了容量缩放思想和最小费用流特性的高效算法。 问题描述 考虑一个有向图G=(V,E)，其中： 每条边(u,v)∈E有容量c(u,v)≥0和费用a(u,v)∈ℝ 每个顶点v∈V有需求b(v)∈ℝ，且∑b(v)=0 目标是找到流f:E→ℝ，满足流量守恒和容量约束，且总费用∑a(u,v)f(u,v)最小 算法核心思想 成本缩放算法通过逐位处理费用的二进制表示，从最高位开始逐步细化费用近似值，利用缩放技术将原问题分解为一系列更易求解的子问题。 求解步骤 步骤1：问题预处理 首先将费用值归一化。假设所有费用均为整数（可通过适当缩放实现），令C=max|a(u,v)|，则费用可用⌈log₂(C+1)⌉位二进制表示。 初始化缩放参数k=⌈log₂C⌉，此时所有边费用近似为aₖ(u,v)=0。 步骤2：外层缩放循环 对于k从⌈log₂C⌉递减到0执行： 计算当前缩放级别的费用：aₖ(u,v)=⌊a(u,v)/2ᵏ⌋ 此时费用近似值aₖ与实际费用a满足：0≤a(u,v)-2ᵏaₖ(u,v)≤2ᵏ-1 步骤3：内层循环 - 改进当前解 在当前费用尺度aₖ下，通过一系列最短路径增广改进流： 构造残量网络G_ f，其中边的费用为aₖ(u,v) 在G_ f中寻找负费用环（使用Bellman-Ford或动态规划） 若存在负费用环，则沿环增广流量（环上最小残量容量） 重复直到无负费用环存在 步骤4：解的精化 当k减少时，费用近似更加精确。关键观察是：上一尺度的最优解是当前尺度的2-近似解，因此只需有限次增广即可达到新尺度最优。 步骤5：终止条件 当k=0时，得到的解即为原问题的最优解，因为此时费用近似值等于实际费用。 算法复杂度分析 外层循环：O(logC)次 每层内循环：O(mn)次增广（使用动态规划找负环） 总复杂度：O(mnlogC) 实例演示 考虑简单网络：顶点{s,1,2,t}，边： s→1：容量3，费用5 s→2：容量2，费用8 1→2：容量4，费用2 1→t：容量2，费用3 2→t：容量3，费用4 需求：b(s)=-3, b(t)=3, 其他为0 执行过程 ： C=8, k=3：所有边费用近似为0，任意可行流均为最优 k=2：费用近似{1,2,0,0,1}，开始寻找负费用环改进 逐步细化至k=0，得到最小费用流：s→1→t流2单位，s→2→t流1单位 成本缩放算法的优势在于将复杂的最小费用流问题分解为多个结构相似的子问题，每个子问题相对容易求解，且具有良好的理论保证。