第 5.14 章：网络流与二分图匹配

5.14.0 从一道题出发：挤奶分配

先看一道 USACO 风格的题：

🐄 题目：挤奶分配 Farmer John 有 N 头奶牛（N ≤ 200）和 M 个牛棚（M ≤ 200）。牛棚 i 最多容纳 c[i] 头奶牛（0 ≤ c[i] ≤ 200）。 每头奶牛有一个偏好牛棚列表——它只肯住进列表中的牛棚，且每头奶牛最多占一个位置。 求最多能安排多少头奶牛住进自己接受的牛棚。

样例：

N=3, M=2, c = [2, 2]
奶牛 1 的偏好：{1, 2}
奶牛 2 的偏好：{1, 2}
奶牛 3 的偏好：{1, 2}
答案：3（牛棚 1 住 2 头，牛棚 2 住 1 头）

先试试你会的方法

思路 1：贪心。 把奶牛逐个塞进「还有空位且在偏好列表里」的牛棚？可惜贪心会错：奶牛 1 先占了牛棚 1 的最后一个位置，可能恰恰堵死了只能住牛棚 1 的奶牛 2，而奶牛 1 本可以改住牛棚 2。「先给谁分配」「优先选哪个棚」都没有能证明正确的顺序——这类「两方匹配、每方有容量」的问题需要反悔机制。

思路 2：二分图匹配？ 把奶牛和牛棚看成二分图的两部，边表示「可住」。普通匹配每个牛棚只能配一头奶牛——但这里牛棚容量是 c[i]（多重匹配）。把牛棚拆成 c[i] 个点？c[i] 总和可达 40000，点数膨胀后普通匈牙利算法 O(V·E) 会退化到 10⁹ 级别，而且拆点代码繁琐。

关键观察： 「反悔机制」正是本章主角网络流的拿手好戏——它的核心操作「沿反向边退流」天生就是反悔。而容量 c[i] 在网络流里只是一条边的容量，连拆点都不用。建图只要三步：

源点 S ──容量 1──► 每头奶牛 ──容量 1──► 偏好的牛棚 ──容量 c[i]──► 汇点 T

「最多安排多少奶牛」=「这张图从 S 到 T 的最大流」。一行建模，问题解决——剩下的事交给算法。

拆解这道题需要回答的问题

学习目标：

• 理解流网络的三大要素（源点、汇点、容量）与「可行流」的守恒约束
• 掌握增广路与残留网络——「反向边 = 反悔」这一核心直觉
• 理解最小割最大流定理的直觉证明
• 手写 Edmonds-Karp 与 Dinic（struct edge + head/cur 数组风格）
• 掌握匈牙利算法，理解它就是「只有一层的增广路搜索」
• 会用「源点→左部→右部→汇点」的万能建图解决匹配类问题
• 了解最小割的典型应用：最大权闭合子图

5.14.1 流网络：把问题变成「运水」

流网络是一张有向图 G = (V, E)，每条边 (u, v) 有一个容量 c(u, v) ≥ 0；图中有一个特殊的源点 s（只出不进）和汇点 t（只进不出）。直观想象：水从源点出发，沿管道（边）流向汇点，管道的粗细就是容量。

一个可行流 f 给每条边分配一个流量 f(u, v)，满足两条约束：

1. 容量限制： 0 ≤ f(u, v) ≤ c(u, v)——管道不能超载；
2. 流量守恒： 除 s、t 外，每个点「流进 = 流出」——中途不产生也不消耗水。

流的值 |f| = 从 s 流出的净流量 = 流入 t 的净流量。最大流问题：求 |f| 的最大值。

割（cut）是把点集分成两半 S 和 T = V \ S，要求 s ∈ S、t ∈ T。割的容量是从 S 指向 T 的所有边的容量之和。直觉上：割就是把水管「一刀切断」，切掉的总粗细就是这一刀的容量——水不可能以超过这个速率通过。

增广路：流是怎么长出来的

残留网络 G_f 是理解一切最大流算法的钥匙。对当前流 f：

• 每条边 (u, v) 的剩余容量 = c(u, v) - f(u, v)（还能再塞多少水）；
• 同时每条边对应一条反向边 (v, u)，剩余容量 = f(u, v)（已塞的水可以退回去）。

增广路是残留网络中一条 s → t 的路径。沿它推流量 Δ（Δ = 路径上剩余容量的最小值，即瓶颈），总流量增加 Δ：正向边剩余容量减 Δ，反向边剩余容量加 Δ。

为什么需要反向边？ 看这个经典例子（ capacities 标在边上）：

     1         1
 s ────► u ────► t          第一轮：贪心地沿 s→u→v→t 推 1 单位
 │      ▲    ▲              （u→v 容量 1）
 │ 1    │1   │ 1
 ▼      │    │
 v ────►┘    │  ← 想推 s→v→?→t，v→t 剩 0？不——
      1                     v 的水可以经 v→u 的反向边「反悔」！

第一轮沿 s→u→v→t 推 1 后，如果当初的选择是错的，反向边 (v, u)（剩余容量 1）允许第二轮走 s→v→(反悔)u→t：u→v 上的 1 单位流量被抵消，等价于「u 的水走上面、v 的水走下面」。反向边的本质是反悔——它保证我们不依赖任何「选路顺序正确」的假设。

最小割最大流定理

定理： 最大流的值 = 最小割的容量。

直觉证明： 一方面任何流 ≤ 任何割（水穿过任何一刀的速率受限于刀口的粗细）。另一方面，当增广结束（残留网络中 s 到不了 t）时，令 S = 残留网络中 s 可达的点集，T = 其余。从 S 到 T 的每条原边必然满流（否则残留网络里 s 能再走一步），从 T 到 S 的每条边必然零流（否则反向边会让 s 可达 T 中的点）。于是穿过这一割的净流量恰好等于割的容量——流顶到了割的上界，说明这个流是最大的，这个割是最小的。∎

这给了一个对拍神器：最大流的答案 = 图上所有 s-t 割容量的最小值，小图可以暴力枚举点集划分来验证。

5.14.2 Ford-Fulkerson 框架与 Edmonds-Karp

Ford-Fulkerson 框架： 反复在残留网络中找一条增广路并增广，直到找不到为止。它只是一个框架——「怎么找增广路」决定了复杂度。若用 DFS 随便找，整数容量下每轮至少推 1，复杂度 O(E·|f|)，容量大时会卡死。

Edmonds-Karp（EK）： 用 BFS 找增广路——每次找边数最少的增广路。可以证明每条边最多成为 O(V) 次「瓶颈」，总轮数 O(VE)，故总复杂度 O(VE²)。V、E ≤ 10³ 级别够用；更大的图交给 Dinic。

实现上有一个竞赛通用技巧：边成对存储，编号从 0 开始，则编号 i 与 i ^ 1 互为反向边——^1 一位运算就能翻转到反向边。

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

struct EK {
    struct Edge { int to, cap; };
    vector<Edge> edges;
    vector<vector<int>> g;   // g[u]：u 的出边编号列表
    vector<int> pre;         // pre[v]：BFS 中到达 v 的边编号（前驱边）

    EK(int n) : g(n), pre(n) {}

    void addedge(int u, int v, int w) {
        g[u].push_back(edges.size()); edges.push_back({v, w});      // 正向边
        g[v].push_back(edges.size()); edges.push_back({u, 0});      // 反向边容量 0
    }

    int maxflow(int s, int t) {
        int flow = 0;
        while (true) {
            // BFS 找一条 s→t 的最短增广路
            fill(pre.begin(), pre.end(), -1);
            pre[s] = -2;                       // 标记 s 已访问（-2 不会撞上边编号）
            queue<int> q; q.push(s);
            while (!q.empty() && pre[t] == -1) {
                int u = q.front(); q.pop();
                for (int id : g[u])
                    if (edges[id].cap > 0 && pre[edges[id].to] == -1) {
                        pre[edges[id].to] = id;
                        q.push(edges[id].to);
                    }
            }
            if (pre[t] == -1) break;           // 残留网络到不了 t：已是最大流
            // 沿前驱边回溯，找瓶颈
            int aug = INF;
            for (int v = t; v != s; v = edges[pre[v] ^ 1].to)
                aug = min(aug, edges[pre[v]].cap);
            // 再回溯一遍更新容量：正向 -aug，反向 +aug
            for (int v = t; v != s; v = edges[pre[v] ^ 1].to) {
                edges[pre[v]].cap -= aug;
                edges[pre[v] ^ 1].cap += aug;
            }
            flow += aug;
        }
        return flow;
    }
};

int main() {
    // 验证样例：s=0, t=3
    // 边：0→1(3), 0→2(2), 1→3(2), 1→2(1), 2→3(3)
    EK ek(4);
    ek.addedge(0, 1, 3);
    ek.addedge(0, 2, 2);
    ek.addedge(1, 3, 2);
    ek.addedge(1, 2, 1);
    ek.addedge(2, 3, 3);
    printf("%d\n", ek.maxflow(0, 3));   // 输出 5
    return 0;
}

样例手算： 割 {0} 容量 3+2=5，割 {0,1,2} 容量 2+3=5，没有更小的割——由最小割最大流定理答案为 5。EK 的运行：第一轮 BFS 找到 0→1→3 推 2，第二轮 0→2→3 推 2，第三轮 0→1→2→3 推 1，共 5 ✓。

回溯的小技巧： edges[pre[v] ^ 1].to 就是路径上 v 的前一个点——反向边的终点即正向边的起点。

5.14.3 Dinic：分层图 + 当前弧

EK 每轮只推一条路，太浪费。Dinic 的改进是分两个阶段：

1. BFS 分层： 在残留网络上从 s 做 BFS，得每个点的层数 dep[u]（s 在第 0 层）。
2. DFS 多路增广： 只允许从第 d 层流向第 d+1 层，DFS 中一次递归把沿途能推的流量全推完（多路增广），直到这一层的所有路都堵死（阻塞流），再重新分层。

每轮分层后 s 到 t 的最短距离严格增加（可证），故最多 V 轮；单轮 DFS 用当前弧优化后是 O(VE)。总复杂度 O(V²E)——竞赛中 Dinic 的实际运行速度远好于理论上界，是当之无愧的主力。

当前弧优化： DFS 中每个点 u 维护「当前试到哪条边」的指针 cur[u]。如果某条出边已经推到极限（或其下游已满），u 之后的流量不必再碰这条边——指针只进不退。没有它复杂度是错的；有了它，一条边被「放弃」后就永远不再被扫描。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10010;    // 点数上限
const int MAXM = 200010;   // 边数上限（已含两倍冗余）
const int INF = 1e9;

struct Edge { int to, nxt, cap; } e[MAXM];
int head[MAXN], cur[MAXN], dep[MAXN], cnt = 0;

void addedge(int u, int v, int w) {
    e[cnt] = {v, head[u], w}; head[u] = cnt++;   // 正向边
    e[cnt] = {u, head[v], 0}; head[v] = cnt++;   // 反向边容量 0
}

bool bfs(int s, int t) {
    memset(dep, -1, sizeof(int) * (t + 2));
    queue<int> q;
    dep[s] = 0; q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; ~i; i = e[i].nxt)
            if (dep[e[i].to] == -1 && e[i].cap > 0) {
                dep[e[i].to] = dep[u] + 1;
                q.push(e[i].to);
            }
    }
    return dep[t] != -1;        // 到不了 t：增广结束
}

int dfs(int u, int inFlow, int t) {
    if (u == t) return inFlow;
    int outFlow = 0;
    for (int &i = cur[u]; ~i; i = e[i].nxt) {    // 注意：i 是 cur[u] 的引用！
        int v = e[i].to;
        if (dep[v] == dep[u] + 1 && e[i].cap > 0) {
            int d = dfs(v, min(inFlow - outFlow, e[i].cap), t);
            if (d > 0) {
                e[i].cap -= d;
                e[i ^ 1].cap += d;
                outFlow += d;
                if (outFlow == inFlow) return outFlow;   // u 的流量用完了
            }
        }
    }
    return outFlow;
}

long long dinic(int s, int t) {
    long long maxflow = 0;
    while (bfs(s, t)) {
        memcpy(cur, head, sizeof(int) * (t + 2));   // 每轮把 head 复制到 cur
        maxflow += dfs(s, INF, t);
    }
    return maxflow;
}

int main() {
    // 与 5.14.2 相同的验证样例，期望 5
    memset(head, -1, sizeof head);
    addedge(0, 1, 3);
    addedge(0, 2, 2);
    addedge(1, 3, 2);
    addedge(1, 2, 1);
    addedge(2, 3, 3);
    printf("%lld\n", dinic(0, 3));   // 输出 5
    return 0;
}

三个实现细节务必想清楚：

1. for (int &i = cur[u]; ...) 中 i 是引用——循环变量前进就是 cur[u] 前进，这是当前弧优化的全部实现，删掉这个 & 复杂度就错了。
2. 每轮 BFS 后要 memcpy(cur, head, ...) 重置当前弧——上一轮的指针位置对本轮无意义。
3. head 初始化为 -1（链式前向星的链尾标记），加边前别忘了 memset(head, -1, ...)。

5.14.4 二分图匹配

二分图：顶点能分成左右两部，所有边都横跨两部（可以想象成「奶牛 ↔ 牛棚」）。匹配是选出一些边使它们没有公共顶点；最大匹配是选得最多的匹配。

匹配中的增广路

在匹配语境下，增广路是一条从未匹配的左点出发、交替经过「非匹配边 → 匹配边 → 非匹配边 → …」最后到达未匹配右点的路径。把路上所有边「非匹配↔匹配」翻转，匹配数加 1：

匹配边用 = 表示，非匹配边用 - 表示：

翻转前： L1 -  R1 = L2 -  R2        （L1、R2 未匹配）
翻转后： L1 =  R1 - L2 =  R2        （匹配数 +1）

匈牙利算法（Kuhn 算法）：对每个未匹配的左点 u 做 DFS 找增广路。遇到右点 v：若 v 空闲，直接配对；若 v 已有对象 w，就递归地请 w 挪窝——w 能找到新欢就让位，否则换下一条边。一次尝试 O(E)，总共 n 次，复杂度 O(VE)。

#include <bits/stdc++.h>
using namespace std;

int n, m, e;           // 左部 n 个点、右部 m 个点
vector<vector<int>> g; // g[u]：左点 u 能连到的右点
vector<int> matchR;    // matchR[v]：右点 v 匹配的左点（-1 未匹配）
vector<int> vis;       // 本轮增广中右点是否访问过

bool tryKuhn(int u) {
    for (int v : g[u]) {
        if (vis[v]) continue;
        vis[v] = 1;
        if (matchR[v] == -1 || tryKuhn(matchR[v])) {  // v 空闲，或原配能挪窝
            matchR[v] = u;
            return true;
        }
    }
    return false;
}

int main() {
    scanf("%d %d %d", &n, &m, &e);
    g.assign(n + 1, {});
    matchR.assign(m + 1, -1);
    vis.assign(m + 1, 0);
    for (int i = 0; i < e; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        g[u].push_back(v);
    }
    int matching = 0;
    for (int u = 1; u <= n; u++) {
        fill(vis.begin(), vis.end(), 0);   // 每轮清空 vis
        if (tryKuhn(u)) matching++;
    }
    printf("%d\n", matching);
    return 0;
}

验证样例： 左 4 点、右 4 点，边 1-1, 1-2, 2-1, 3-2, 3-3, 4-3, 4-4 → 输出 4。手算：u1 配 r1；u2 想要 r1，请原配 u1 挪去 r2，成功（u2=r1）；u3 配 r3；u4 想要 r3，u3 试图挪去 r2、但 r2 的原配 u1 已无处可去，u4 改配 r4 → 完美匹配 4 ✓。另一组 1-1, 1-2, 2-1, 3-2, 3-3（3 左 3 右）→ 输出 3 ✓。

用 Dinic 跑二分图：更快的 O(E√V)

二分图最大匹配 = 网络流特例：源点 → 左部（容量 1）→ 右部（容量 1）→ 汇点。这张图是单位容量网络，Dinic 在其上的复杂度自动优化为 O(E√V)（即 Hopcroft-Karp 算法的效果），比匈牙利的 O(VE) 快一个档次。

经验法则： 普通匹配且规模小 → 匈牙利（好写好调）；规模大或容量不为 1（如本章开篇的挤奶分配）→ 直接上 Dinic 建图，反正是同一套模板。

5.14.5 实战：挤奶分配（Dinic 完整程序）

回到开篇题。建模回顾：S → 奶牛 i（容量 1）→ 偏好牛棚（容量 1）→ T（容量 c[棚]）。最大流 = 最多安排的奶牛数。为什么对？每一单位流对应「一头奶牛住进一个牛棚」：源点边限每牛至多 1、中间边限每对（牛，棚）至多 1、汇点边限每棚至多 c[i]——恰好是原题所有约束，且流的守恒保证「住进」的一致性。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 810;    // 点数：S=1, 奶牛 2..N+1, 牛棚 N+2..N+M+1, T=N+M+2
const int MAXM = 200010; // 边数上限（两倍冗余）
const int INF = 1e9;

struct Edge { int to, nxt, cap; } e[MAXM];
int head[MAXN], cur[MAXN], dep[MAXN], cnt = 0;

void addedge(int u, int v, int w) {
    e[cnt] = {v, head[u], w}; head[u] = cnt++;
    e[cnt] = {u, head[v], 0}; head[v] = cnt++;   // 反向边容量 0
}

bool bfs(int s, int t) {
    memset(dep, -1, sizeof(int) * (t + 2));
    queue<int> q;
    dep[s] = 0; q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; ~i; i = e[i].nxt)
            if (dep[e[i].to] == -1 && e[i].cap > 0) {
                dep[e[i].to] = dep[u] + 1;
                q.push(e[i].to);
            }
    }
    return dep[t] != -1;
}

int dfs(int u, int inFlow, int t) {
    if (u == t) return inFlow;
    int outFlow = 0;
    for (int &i = cur[u]; ~i; i = e[i].nxt) {
        int v = e[i].to;
        if (dep[v] == dep[u] + 1 && e[i].cap > 0) {
            int d = dfs(v, min(inFlow - outFlow, e[i].cap), t);
            if (d > 0) {
                e[i].cap -= d;
                e[i ^ 1].cap += d;
                outFlow += d;
                if (outFlow == inFlow) return outFlow;
            }
        }
    }
    return outFlow;
}

long long dinic(int s, int t) {
    long long maxflow = 0;
    while (bfs(s, t)) {
        memcpy(cur, head, sizeof(int) * (t + 2));
        maxflow += dfs(s, INF, t);
    }
    return maxflow;
}

int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    vector<int> c(M + 1);
    for (int i = 1; i <= M; i++) scanf("%d", &c[i]);

    int S = 1, T = N + M + 2;
    memset(head, -1, sizeof(int) * (T + 2));
    for (int i = 1; i <= N; i++) {
        addedge(S, 1 + i, 1);                    // 源点 → 奶牛，容量 1
        int k; scanf("%d", &k);
        while (k--) {
            int b; scanf("%d", &b);
            addedge(1 + i, 1 + N + b, 1);        // 奶牛 → 偏好牛棚，容量 1
        }
    }
    for (int b = 1; b <= M; b++)
        addedge(1 + N + b, T, c[b]);             // 牛棚 → 汇点，容量 c[b]

    printf("%lld\n", dinic(S, T));
    return 0;
}

输入格式约定： 第一行 N M；第二行 M 个整数 c[1..M]；接下来 N 行，每行先一个 k（偏好数），后跟 k 个牛棚编号。

样例验证（手算）：

输入：
3 2
2 2
2
1 2
2
1 2
2
1 2

输出：3

容量检查：S 出 3 条容量 1 的边（总出量 ≤ 3），T 入 2 条容量 2 的边（总入量 ≤ 4），中间 6 条容量 1。增广：奶牛 1 → 棚 1，奶牛 2 → 棚 1（容量 2 用满），奶牛 3 → 棚 2。最大流 3 ✓。

再测容量不足的情形：3 2 / 1 1 / 2: 1 2 / 2: 1 2 / 2: 1 2 → 棚 1、棚 2 各容 1，答案 2 ✓（程序实测输出 2）。第三组：4 2 / 1 1 / 1: 1 / 1: 1 / 1: 1 / 1: 1 → 4 头牛抢 2 个容量 1 的棚，答案 2 ✓。

规模分析： 点数 ≤ N+M+2 ≈ 402，边数 ≤ N+2·Σk+M ≈ 200+80000+200，Dinic 在二分图上 O(E√V) ≈ 8×10⁴ × 20 = 1.6×10⁶，毫秒级。

5.14.6 最小割的应用：最大权闭合子图

最大流难的不是算法（模板背熟即可），而是建模。最小割最大流定理的威力的一个经典展示：

最大权闭合子图问题： 有 n 个物品，物品 i 有权 w[i]（可正可负），且存在依赖关系「选了 a 就必须选 b」。选一个闭合（依赖都满足）的子集，使权和最大。

建模： 源点 S → 每个正权点（容量 w[i]），每个负权点 → 汇点 T（容量 -w[i]），依赖 a → b 连容量 +∞ 的边。

答案 = 正权总和 − 最小割。 直觉：一个 S-T 割对应一种「选/不选」的划分决策——∞ 边永不会被割断，保证依赖闭合；割掉 S→i 表示「放弃正权点 i」（损失 w[i]），割掉 j→T 表示「接受负权点 j」（付出 -w[j]）。最小割 = 最小的「总损失」，所以最大权和 = 全部正权 − 最小损失。跑一遍 Dinic 即可，这类题在 Platinum 的「收益/代价二选一」模型中反复出现。

最小割直接可解的还有：二分图最小点覆盖（= 最大匹配，König 定理）、最长反链等——核心都是把「互斥的二选一」翻译成割边。

5.14.7 ⚠️ 常见错误辨析

详解错误 1（最高频）： 反向边容量 0 的意义是「初始没有流量可退」。若误设为 w，算法会在从未流过水的边上「无中生有」地退流，总流量超过真实最大流。这种错误在小图上一定对拍得出：暴力枚举所有 S-T 割取最小值，与程序输出比对。

详解错误 2： cur 是「本轮流分层图中的进度指针」。新一轮 BFS 后分层完全变了，上一轮被放弃的边这一轮可能重新可用。忘复制时 cur 停在链表深处，DFS 直接从旧位置扫——要么漏增广路（答案小），要么在自环状残留结构里转不出来。

5.14.8 本章总结

📌 核心要点

🔗 与前后章节的联系

• 第 5 部分（图论基础）： BFS 的分层用法在本章出现第二次（第一次是最短路）；链式前向星存图在 Dinic 中是标配。
• 第 5.9 章（MST）的并查集思路： 割的概念与 Kruskal 的「连通分量合并」互为镜像——一个在切、一个在连。
• Platinum 预告： 网络流是 USACO Platinum 的高频主题：费用流、上下界流、最大权闭合子图的变体（「收益选择」类题）。本章的 Dinic 模板要练到闭眼默写。

🏋️ 练习题

🟢 简单

5.14-E1. 棋盘覆盖 给定 N × M 的棋盘，某些格子是障碍。用 1×2 的多米诺骨牌覆盖无障碍格子，要求不重叠、不越界、不压障碍。求最多能放多少张骨牌。 数据规模： 1 ≤ N, M ≤ 100。

🟡 中等

5.14-M1. 最小路径覆盖 给定 N 个顶点、M 条边的有向无环图，用若干条顶点不相交的有向路径覆盖所有顶点（路径可以为单点），求最少路径数。 数据规模： 1 ≤ N ≤ 200，0 ≤ M ≤ 6000。（经典题，DAG 最小路径覆盖）

🔴 困难

5.14-H1. 太空探测计划 （最大权闭合子图，经典「太空飞行计划问题」变体） 有 E 个实验和 I 种仪器。做实验 i 得到报酬 p[i]；实验 i 需要用到一组仪器，仪器 j 的购置费用为 c[j]（一个仪器可被多个实验共用）。只有「买齐所需仪器」才能做实验。选择一个实验子集，最大化「总报酬 − 总购置费」。 数据规模： 1 ≤ E ≤ 100，1 ≤ I ≤ 50，1 ≤ p[i], c[j] ≤ 100。