网络流是图论中研究"流量"在带容量网络中如何分配的框架。最大流、最小割、费用流是三大核心问题，广泛应用于匹配、调度、资源分配等场景。
一、基本概念
Mermaid · 渲染中（下方为源码）
graph LR S((源s)) --> A[中间节点] A --> T((汇t)) S -.容量c.-> A A -.流量f.-> T
- 源点 s：流的起点
- 汇点 t：流的终点
- 容量 c(u,v)：边 (u,v) 的最大流量
- 流量 f(u,v)：边 (u,v) 的实际流量
- 约束：0 ≤ f(u,v) ≤ c(u,v)，流量守恒（除 s、t 外入=出）
二、最大流问题
求从 s 到 t 的最大总流量。
Ford-Fulkerson 思想
- 找一条从 s 到 t 的增广路（残余容量 > 0）
- 沿增广路推送尽可能多的流量
- 重复直到无增广路
Edmonds-Karp（BFS 找增广路）
int maxFlow(int[][] capacity, int s, int t) {
int n = capacity.length;
int[][] residual = new int[n][n]; // 残余网络
for (int i = 0; i < n; i++) residual[i] = capacity[i].clone();
int flow = 0;
int[] parent = new int[n];
while (bfs(residual, s, t, parent)) {
// 找增广路上的最小残余容量
int pathFlow = Integer.MAX_VALUE;
for (int v = t; v != s; v = parent[v]) {
pathFlow = Math.min(pathFlow, residual[parent[v]][v]);
}
// 更新残余网络
for (int v = t; v != s; v = parent[v]) {
int u = parent[v];
residual[u][v] -= pathFlow;
residual[v][u] += pathFlow; // 反向边
}
flow += pathFlow;
}
return flow;
}
boolean bfs(int[][] residual, int s, int t, int[] parent) {
Arrays.fill(parent, -1);
parent[s] = s;
Queue<Integer> q = new LinkedList<>();
q.offer(s);
while (!q.isEmpty()) {
int u = q.poll();
for (int v = 0; v < residual.length; v++) {
if (parent[v] == -1 && residual[u][v] > 0) {
parent[v] = u;
if (v == t) return true;
q.offer(v);
}
}
}
return false;
}