寻求满足边流量平方成本约束、实现流量均匀分配的Min Cost Max Flow算法

你遇到的是典型的凸费用流问题，流量平方为严格凸函数，最小化总费用的过程本身就会驱动流量在边之间均匀分配，目前有三类成熟的落地方案：

方案1：拆边法（实现成本最低，兼容传统MCMF框架） #

• 核心逻辑：将平方费用拆解为多段单位费用递增的单位流量边，把凸费用转化为传统最小费用最大流支持的单位边费用形式，无需修改现有MCMF算法代码即可直接求解
• 具体实现：假设某条边最大容量为C，原费用函数为f(x) = a*x²（a为费用系数，所有边取相同a即可实现均匀分配目标），流量每增加1单位的边际费用为a*(x² - (x-1)²) = a*(2x-1)，将原边拆分为C条容量为1的边，每条的单位费用依次为a*1、a*3、a*5…a*(2C-1)即可
• 适用场景：单条边容量<1000的中小规模场景，运行效率足够稳定
• 优化技巧：如果单条边容量极大，可将边际费用增量相同的连续流量段合并为大容量边，大幅降低总边数

方案2：边际费用动态计算法（适合单条边容量极大的场景） #

• 核心逻辑：无需预拆边，在每次增广时动态计算每条边当前的边际费用，找源汇点之间的最小边际费用增广路，单次增广1单位流量，直到达到最大流阈值或无增广路
• 具体实现：每条边维护当前已用流量f，增广前计算新增1单位流量的边际费用a*((f+1)² - f²)作为当前边的临时单位费用，跑最短路找增广路，增广完成后更新边的已用流量即可
• 适用场景：单条边容量极大但总最大流规模不大的场景，避免拆边导致的边数爆炸

方案3：凸费用流专用算法（适合大规模工业场景） #

• 核心逻辑：直接使用针对凸费用优化的专用网络流算法，比如成本缩放（Cost Scaling）算法，这类算法专门适配凸费用的最小成本流问题，时间复杂度远低于前两种方案
• 注意事项：需要自行实现专用算法框架，无法直接复用传统MCMF的代码，适合边数过万、流量过万的大规模业务场景

上述三类方案的最优解都天然满足流量均匀分配的需求，可根据你的业务规模、现有代码基础选择对应的实现方式。

内容的提问来源于stack exchange，提问作者SaeedOB