一、为什么学最小费用最大流？
Mermaid · 渲染中（下方为源码）
graph LR S((s)) --> A[残余网络找最短路] A --> T((t)) T --> B[沿路增广] B --> A
在最大流基础上，每条边有单位费用 cost(u,v)，目标是在流量最大的前提下使总费用最小。应用：
- 运输问题、任务分配（带成本）
- 最小费用匹配
- 流量有成本约束的调度
二、基本思想
在残余网络上反复用 SPFA / Dijkstra（势优化） 找从 s 到 t 的单位费用最短路，沿该路增广，直到无增广路。
- 反向边费用为
−cost，用于"退流" - 要求无负环（初始无负费用环即可）
三、SPFA 版实现
static int[] dist = new int[N];
static int[] preV = new int[N], preE = new int[N];
static boolean[] inq = new boolean[N];
static final int INF = 1 << 29;
boolean spfa(int s, int t) {
Arrays.fill(dist, INF);
Arrays.fill(inq, false);
dist[s] = 0;
Queue<Integer> q = new LinkedList<>(); q.offer(s); inq[s] = true;
while (!q.isEmpty()) {
int u = q.poll(); inq[u] = false;
for (int i = head[u]; i != -1; i = nxt[i]) {
if (cap[i] > 0 && dist[v[i]] > dist[u] + cost[i]) {
dist[v[i]] = dist[u] + cost[i];
preV[v[i]] = u; preE[v[i]] = i;
if (!inq[v[i]]) { q.offer(v[i]); inq[v[i]] = true; }
}
}
}
return dist[t] != INF;
}
int minCostMaxFlow(int s, int t) {
int flow = 0, fee = 0;
while (spfa(s, t)) {
int f = INF;
for (int x = t; x != s; x = preV[x]) f = Math.min(f, cap[preE[x]]);
for (int x = t; x != s; x = preV[x]) {
int e = preE[x];
cap[e] -= f; cap[e ^ 1] += f;
}
flow += f; fee += f * dist[t];
}
return fee; // 总费用；flow 即最大流
}