xxx 最小费用最大流问题（Cycle Canceling算法） 题目描述 给定一个带权有向图G=(V,E)，其中每条边e=(u,v)有两个属性：容量c(e)≥0表示最大流量，费用w(e)表示单位流量的成本。设源点s和汇点t，求从s到t的最大流f，使得总运输成本∑(w(e)·f(e))最小。 核心概念 这是最小费用最大流问题，需要同时满足两个目标：流量最大化、总成本最小化。Cycle Canceling算法通过消除负费用环来优化成本。 基础准备 残余网络 ：对当前流f，构建残余图G_ f=(V,E_ f) 对于原边e=(u,v)∈E，若f(e)<c(e)，添加正向边(v,u)，残余容量c_ f(e)=c(e)-f(e)，费用w_ f(e)=w(e) 添加反向边(v,u)，残余容量c_ f(e)=f(e)，费用w_ f(e)=-w(e)（允许回流减费） 负环定理 ：流f是最小费用流当且仅当残余网络G_ f中没有负费用圈。 算法步骤 初始可行流 ：先用任意最大流算法（如Edmonds-Karp）求初始最大流f₀ 循环消负环 ： a. 构建当前流f的残余网络G_ f b. 在G_ f中寻找负费用圈C（用Bellman-Ford等算法） c. 若不存在负圈，终止并输出f作为最优解 d. 若存在负圈C，计算圈中最小残余容量δ=min{c_ f(e)|e∈C} e. 沿圈C推送δ单位流量（正向边增加δ，反向边减少δ） f. 更新流f，返回步骤a 实例演示 考虑简单网络：顶点{s,a,b,t}，边： s→a: 容量5,费用2 s→b: 容量3,费用1 a→b: 容量2,费用-1 a→t: 容量4,费用3 b→t: 容量6,费用2 执行过程 ： 初始最大流f₀：s→a→t(4), s→b→t(3)，总流量7，成本=4×2+3×1+4×3+3×2=29 第一次迭代： 残余网络中发现负圈s→b→a→s（费用1+(-1)+(-2)=-2） 沿圈推送δ=2流量：s→b增2, b→a增2, a→s减2（反向边） 新流：s→a:2, s→b:5, a→t:4, b→t:5, a→b:2 成本=2×2+5×1+4×3+5×2+2×(-1)=25 第二次迭代： 残余网络中无负圈，终止。最终成本25优于初始29。 复杂度分析 最坏情况：每次消环减少1单位成本，复杂度O(|V|·|E|·C·W)（C最大容量，W最大费用） 实际常用Capacity Scaling等优化提升效率 关键理解点 负圈推送相当于在保持流量的前提下调整流分布以降低成本 算法保证在有限步内收敛，因为总成本每次严格下降 初始流只需满足可行性，最优性通过消环逐步逼近