如何实现最小费用最大流？
题目与使用场景
网络每条边有容量和单位费用，要求从 s 到 t 发送最多 limit 的流量，并在流量相同的方案中费用最小。实现需要返回实际流量和费用，处理反向残量边、负费用、并行边、不可达和整数溢出。
面试官考察什么
- 是否正确建立残量网络和反向边费用。
- 能否用连续最短增广路或势能重标定处理负边。
- 是否区分最大流量目标与最小费用次目标。
- 能否给出复杂度、溢出边界和性质测试。
作答前的澄清问题
确认容量和费用是否为整数、是否允许负费用环、是否要求精确 limit、图规模和费用上界。若有负费用环，需说明模型是否允许无界降费，以及初始势能如何求得。
30 秒回答框架
每条输入边建立正向容量和反向容量为零的残量边，反向费用取相反数。反复在残量网络中寻找 s 到 t 的最短路，沿路增广瓶颈流量，直到达到 limit 或不存在路径。若边费用可能为负，先用 Bellman-Ford 求初始势能，之后用势能重标定让边费用非负，再用 Dijkstra。总复杂度取决于增广次数和最短路实现，不能只报普通最大流复杂度。
分步骤深入解答
1. 残量边结构
边记录终点、反向索引、剩余容量和费用。增广时减少正向容量、增加反向容量；费用乘以增广流量累加。反向边允许算法撤销早期选择，是费用最优的关键。
2. 最短路与势能
若所有费用非负，Dijkstra 足够。存在负费用但没有负环时，维护每个点的势能，使用重标定后的费用计算最短路，再更新势能。若初始费用含负值，不能直接把普通 Dijkstra 当作正确算法。
3. 增广与停止
每次增广量是 limit 剩余量、路径瓶颈和可选批量的最小值。路径不存在时停止并返回当前流量；若必须达到 limit，则报告不可行。费用用足够宽的整数类型，并在加法前检查乘法溢出。
高质量示范回答
我会用邻接表保存残量边，每次 addEdge 同时加入正向和反向边。主循环在残量容量为正的图上寻找最短 s 到 t 路径，沿路径增广并更新费用。无负费用时用 Dijkstra；有负费用但无负环时先求初始势能，再用 reduced cost 保持非负。每轮把增广量限制为目标剩余、路径瓶颈和边容量。无法继续时返回实际流量；若小于目标则标记不可行。测试覆盖反向撤销、并行边、零容量、负费用、断开图、达到部分流量、负环约束和大费用溢出。最小费用最大流与 OR-Tools 的模型一致，但具体复杂度要按增广次数、节点和边数说明，不能假设总是多项式于数值容量。
常见错误
- 忘记加入反向边或把反向费用设为正数。
- 在存在负费用边时直接使用 Dijkstra。
- 找到一条最短路后只增广一单位，导致不必要的运行时间。
- 把“最大流”与“达到目标流量的最小费用”混为一个排序条件。
- 用窄整数累计费用，忽略大容量乘费用的溢出。
追问及应对
为什么反向边能改正之前的选择？
反向边代表撤回已发送的流量，并把相应费用取反。后续最短路可以走反向边，重排流量后得到更低总费用。
什么时候需要 Bellman-Ford？
初始残量图含负费用边且没有负环时，需要它或等价方法计算初始势能；之后 reduced cost 非负即可用 Dijkstra。
如果目标流量达不到怎么办？
停止并返回实际流量和费用，同时明确不可行。若业务必须满足目标，应在调用层回滚或选择备用网络，不能把部分流量冒充成功。