第44讲：网络流进阶——从最小割到费用流，再到二分图
各位同学，今天我们来啃一块硬骨头。网络流进阶，听起来就有点劝退是吧？别急，我当年学这块的时候也头大。但后来在实际项目中用了几次，才发现这东西是真有用。说白了，网络流不只是算法竞赛的玩具，很多工程调度、资源分配问题，最后都能归到这张“网”上。
这一讲，我们聚焦四个核心话题：最小割最大流定理、最小费用最大流（SPFA实现与Dijkstra实现）、以及二分图的最小点覆盖与最大独立集。它们之间有一条隐秘的线索——我习惯称之为“流与割的对偶之美”。
核心思想：最大流 = 最小割。这不是巧合，是线性规划对偶性的直接体现。理解了这个，你再看费用流和二分图，会发现它们都是同一棵树上开出的花。
一、最小割最大流定理——不只是理论
先问个问题：你有一个网络，从源点到汇点，最大能送多少流量？这是最大流问题。那最小割呢？就是找一组边，把它们切掉就能让源点和汇点彻底断开，并且这些边的容量之和最小。
定理说：最大流的值，等于最小割的容量。我第一次看到这个结论时，觉得太漂亮了。后来在项目中做网络带宽规划，我直接用这个定理来评估链路的瓶颈——你想想看，最大流算出来的是实际吞吐量，最小割告诉你的就是哪里最脆弱。
我的经验：在实际工程中，最小割比最大流更有用。比如你要设计一个容灾系统，想知道切断哪些链路代价最小——这就是最小割问题。我曾经帮一个金融客户做网络冗余分析，最后发现最小割恰好落在两条光纤上，而不是我以为的核心交换机。
实现上，我们通常用Dinic或ISAP求最大流，然后从源点在残量网络上做BFS，能到达的点属于S集，其余属于T集。所有从S指向T的边，就是最小割。
// 伪代码：求最小割
int maxflow = dinic(s, t);
// 在残量网络上从s做BFS
bool vis[MAXN];
queue<int> q; q.push(s); vis[s] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
for (每条边 e 从 u 出发) {
if (e.cap > 0 && !vis[e.to]) {
vis[e.to] = true;
q.push(e.to);
}
}
}
// vis[u] == true 的点属于S集，否则属于T集
// 所有从S指向T的边构成最小割二、最小费用最大流——让流量带上价格标签
现实世界哪有免费的流量？每条边除了容量，还有单位流量的费用。你要在保证最大流的前提下，让总费用最小。这就是最小费用最大流问题。
我习惯把它理解为“最便宜的运输方案”。比如你有货物要从工厂送到仓库，每条路有运力限制和运费，怎么运最省钱？
2.1 SPFA实现——简单但慢
SPFA实现的核心思路：每次用SPFA找一条从源点到汇点的最短增广路（以费用为权值），然后沿着这条路尽可能多地增广。重复直到无法增广。
为什么用SPFA？因为它能处理负权边。费用流中反向边的费用是负的，所以Dijkstra不能直接用。
// SPFA实现最小费用最大流
struct Edge {
int to, cap, cost, rev;
};
vector<Edge> G[MAXN];
int dist[MAXN], prevv[MAXN], preve[MAXN];
bool inq[MAXN];
int min_cost_flow(int s, int t, int maxf) {
int res = 0, flow = 0;
while (flow < maxf) {
// SPFA求最短路
fill(dist, dist + MAXN, INF);
queue<int> q;
dist[s] = 0; q.push(s); inq[s] = true;
while (!q.empty()) {
int u = q.front(); q.pop(); inq[u] = false;
for (int i = 0; i < G[u].size(); i++) {
Edge &e = G[u][i];
if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
dist[e.to] = dist[u] + e.cost;
prevv[e.to] = u;
preve[e.to] = i;
if (!inq[e.to]) { q.push(e.to); inq[e.to] = true; }
}
}
}
if (dist[t] == INF) break; // 无法增广
int d = maxf - flow;
for (int v = t; v != s; v = prevv[v])
d = min(d, G[prevv[v]][preve[v]].cap);
flow += d;
res += d * dist[t];
for (int v = t; v != s; v = prevv[v]) {
Edge &e = G[prevv[v]][preve[v]];
e.cap -= d;
G[v][e.rev].cap += d;
}
}
return flow < maxf ? -1 : res; // 返回最小费用
}注意：SPFA在稠密图上可能退化到O(VE)，我曾在一次竞赛中被卡过。如果图比较大，建议用Dijkstra+势能优化。
2.2 Dijkstra实现——更快更稳
Dijkstra不能处理负权边，但我们可以引入“势能”h[v]，把边权变成非负的。具体做法：
- 初始时用SPFA计算每个点的势能h[v]（从源点的最短距离）
- 每次用Dijkstra求最短路时，边权改为：cost + h[u] - h[v]
- 增广后更新势能：h[v] += dist[v]
这样改造后，所有边权非负，Dijkstra就能上场了。时间复杂度降到O(F * E log V)，比SPFA稳定得多。
// Dijkstra + 势能实现最小费用最大流
int h[MAXN]; // 势能
int dist[MAXN], prevv[MAXN], preve[MAXN];
int min_cost_flow_dijkstra(int s, int t, int maxf) {
int res = 0, flow = 0;
fill(h, h + MAXN, 0);
while (flow < maxf) {
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
fill(dist, dist + MAXN, INF);
dist[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto p = pq.top(); pq.pop();
int u = p.second;
if (dist[u] < p.first) continue;
for (int i = 0; i < G[u].size(); i++) {
Edge &e = G[u][i];
int nd = dist[u] + e.cost + h[u] - h[e.to];
if (e.cap > 0 && dist[e.to] > nd) {
dist[e.to] = nd;
prevv[e.to] = u;
preve[e.to] = i;
pq.push({nd, e.to});
}
}
}
if (dist[t] == INF) break;
for (int v = 0; v < MAXN; v++) h[v] += dist[v];
int d = maxf - flow;
for (int v = t; v != s; v = prevv[v])
d = min(d, G[prevv[v]][preve[v]].cap);
flow += d;
res += d * h[t];
for (int v = t; v != s; v = prevv[v]) {
Edge &e = G[prevv[v]][preve[v]];
e.cap -= d;
G[v][e.rev].cap += d;
}
}
return flow < maxf ? -1 : res;
}我的建议：如果图规模不大（V < 1000），SPFA实现更简单，不容易写错。如果图大或者对性能有要求，直接用Dijkstra+势能。我在一个物流调度项目中，用Dijkstra版本把计算时间从3秒降到了0.2秒。
三、二分图的最小点覆盖与最大独立集
这部分内容，说白了就是网络流在二分图上的应用。你可能会问：二分图和网络流有什么关系？
关系大了。二分图的最大匹配可以用最大流求解（源点连左部，左部连右部，右部连汇点，容量全为1）。而最小点覆盖和最大独立集，又能通过最大匹配推导出来。
3.1 最小点覆盖
定义：选最少的点，使得每条边至少有一个端点被选中。
定理（Kőnig定理）：二分图的最小点覆盖 = 最大匹配。
怎么构造？先求最大匹配，然后从左侧所有未匹配点出发，沿着“未匹配边→匹配边→未匹配边→...”交替走，标记所有能到达的点。最后：左侧未标记的点 + 右侧标记的点，就是最小点覆盖。
// 构造最小点覆盖
// 先求最大匹配 matchL[v] = u 表示左侧v匹配右侧u
bool visL[MAXN], visR[MAXN];
void dfs(int u) {
visL[u] = true;
for (int v : adj[u]) {
if (!visR[v]) {
visR[v] = true;
if (matchR[v] != -1 && !visL[matchR[v]])
dfs(matchR[v]);
}
}
}
// 从左侧未匹配点出发
for (int u = 0; u < nL; u++)
if (matchL[u] == -1) dfs(u);
// 最小点覆盖 = 左侧未标记 ∪ 右侧标记3.2 最大独立集
定义：选最多的点，使得任意两点之间没有边相连。
定理：二分图的最大独立集 = 总点数 - 最小点覆盖。
为什么？因为点覆盖覆盖了所有边，剩下的点之间必然没有边相连，所以是独立集。而且这个独立集是最大的。
实用技巧：很多看似不相关的问题，比如“选最多的员工，使得没有上下级冲突”、“安排最多的课程，使得时间不冲突”，本质上都是求最大独立集。我曾在一个人力资源项目中，用这个模型帮HR优化了排班方案，效果立竿见影。
四、总结与避坑
这一讲内容不少，我帮你理一下脉络：
- 最小割最大流定理：最大流的值等于最小割的容量。求最小割就是找残量网络中从源点能到达的点集。
- 最小费用最大流：SPFA实现简单但慢，Dijkstra+势能实现快但复杂。根据场景选。
- 二分图：最小点覆盖 = 最大匹配，最大独立集 = 总点数 - 最小点覆盖。构造方法要记牢。
我曾经踩过的坑：
- 费用流中反向边的费用忘记取负——这是最常见的bug，检查三遍都不为过。
- Dijkstra+势能时，初始势能必须用SPFA算，不能全设为0。否则第一次迭代可能因为负权边出错。
- 二分图构造最小点覆盖时，一定要从左侧未匹配点出发DFS，而不是所有点。
好了，这一讲就到这里。网络流的世界远不止这些，但掌握了最小割、费用流和二分图这三个武器，你已经能解决大部分实际问题了。下次遇到资源分配、路径规划、冲突消解这类问题，不妨想想能不能用网络流建模。