最小费用最大流（Min-Cost Max-Flow, MCMF）：在容量约束下，使从 s 到 t 的总流量最大且总费用最小；典型实现为“势函数 + 最短路增广”，非负边用 Dijkstra，含负边先用 Bellman-Ford 初始化势或直接用 SPFA。常见复杂度 O(F E log V)。
Description: Successive shortest augmenting paths with potentials (Johnson) for min-cost max-flow. Allows negative costs if there is no negative cycle. Time: O(F E log V) with Dijkstra + heap; O(F V E) with SPFA Status: tested
展开阐述
-
接口/数据结构（据实现）
- addEdge(u, v, cap, cost)：加有向边（并建反向边 0 容量、-cost 费用）。
- pair<ll,ll> minCostMaxFlow(s, t)：返回 {flow, cost}，分别为最大流及其最小总费用。
- 内部维护：残量网络、父边 par[]、距离 dist[]、势 pi[] 等。
-
算法流程（势函数 + 增广路）
- 初始化势 pi：若存在负费用边，先用 Bellman-Ford 使所有改权边非负；或在首轮用 SPFA 取代 Dijkstra。
- 每轮：
- 在残量网络上用改权 w’(u,v)=w(u,v)+pi[u]-pi[v] 跑最短路（仅考虑剩余容量>0 的边）。
- 若 t 不可达，算法结束。
- 由 par 回溯得到可增广量 f，沿路推送并记 cost += f · Σ(cost(edge))，flow += f。
- 更新残量与势：对所有可达 v 令 pi[v] += dist[v]，保证下一轮仍无负边。
- 直至无法增广。
-
输出语义
- flow：最大可送达的流量。
- cost：达到该流量的最小总费用。
- 若仅需给定流量 Q 的最小费用，可在累计 flow 达到 Q 时提前退出。
-
复杂度
- Dijkstra + 堆每轮 O(E log V)，轮数为增广次数（至多 F），合计 O(F E log V)。
- 若用 SPFA 求最短路，则 O(F V E)。
-
使用与注意
- 假定无负环；若存在负环，费用可无界下降（需要额外检测/限制）。
- 容量与费用建议使用 64 位，注意乘法溢出。
- addEdge 时务必同步建反向边，保持残量网络闭合。
- 常见应用：带成本的匹配/指派、最小路径覆盖、流量分配、循环流调节等；二分图带权匹配可用费用流或见 079-图论-带权匹配。