二分图匹配与最大流

前言

上一章我们处理的问题都是”能不能到达""最短距离多少”。这一章的问题更复杂——不只是”到不到得了”，而是”能流多少”。

想象一个自来水管网：水厂（源点）通过管道向城市（汇点）输水。每根管道有容量限制。最大流就是：从水厂到城市，最多能输送多少水？

这个问题看似和图遍历无关，但它的求解方法——Ford-Fulkerson ——本质上就是反复找”增广路”（还能多流水的路径）。增广路？这不就是 BFS/DFS 找路径吗？图遍历的思想在这里以新的面貌出现。

最大流有一个出人意料的应用：二分图最大匹配。二分图是”可以分成左右两列，所有边都跨列”的图。匹配是”选一些边，每个节点最多连一条”。最大匹配就是”最多选几条边”。建一个虚拟的源点和汇点，最大匹配就变成了最大流问题。

教材（Tessoku Book 9.8 B68 ALGO Express 和 9.9 B69 Black Company 2）详细展示了最大流/最小割的建模技巧——如何把看似和图无关的优化问题转化为最大流。

问题的本质

什么是二分图？

二分图（Bipartite Graph）是指顶点可以分成两组 $L$ 和 $R$，所有边都只连接 $L$ 中的点和 $R$ 中的点——组内没有边。

判断二分图的方法：能否用两种颜色给所有节点染色，使相邻节点颜色不同？ 这等价于 BFS/DFS 染色——从任意节点开始染白色，它的邻居染黑色，邻居的邻居染白色……如果某个节点需要同时染白色和黑色，就不是二分图。

二分图等价于”图没有奇数长度的环”。为什么？因为沿着环走一圈，每次过边换颜色，走偶数步回到起点颜色不变，走奇数步颜色变了——矛盾。

匹配是什么？

在二分图中，匹配是一组边的集合，其中每个节点最多出现在一条边上。可以理解为”配对”——每个左边的点最多配一个右边的点，反之亦然。最大匹配就是配对数最多的匹配。

经典例子：$N$ 个工人和 $M$ 个任务，每个工人能胜任若干任务。最大匹配就是”最多分配几个工人去干不同的任务”。

最大流：管网能流多少水？

流网络是一个有向图，每条边有一个容量上限。有一个源点 $s$（水厂）和一个汇点 $t$（城市）。流要满足：

1. 每条边上的流量 $\le$ 容量
2. 除 $s$ 和 $t$ 外，每个节点的流入量 = 流出量（流量守恒）

最大流就是从 $s$ 到 $t$ 的总流量最大值。

Ford-Fulkerson 方法：反复在”残余图”上找 $s$ 到 $t$ 的增广路（BFS 或 DFS），沿路增加流量。残余图中的反向边是关键——它允许”撤回”之前的流，把水重新分配到更优的路径。

最大流 = 最小割：图论最美的定理

割是把图分成两半（$S$ 含 $s$，$T$ 含 $t$），割的容量是所有从 $S$ 到 $T$ 的边的容量之和。直观上，割就是”切断水管的代价”。

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

为什么？想象水管网络。最大流是你能送多少水。最小割是”最少切断多少容量的管子就能完全阻断水流”。如果你能送 $F$ 单位的水，那切断容量 $< F$ 的管子不可能堵住所有水——至少有 $F$ 单位在流。所以最小割 $\ge$ 最大流。反过来，最大流达到后，沿着”满流的边”走，就能找到一个割恰好等于最大流——所以最小割 $\le$ 最大流。两者相等。

教材 9.8 B68 ALGO Express 巧妙地利用了这个定理：把”选不选特急站”的决策转化为最小割问题。不选 = 切断 $s \to i$ 的边，选 = 切断 $i \to t$ 的边，约束条件 = $\infty$ 容量的边。最小割自然满足所有约束——因为违反约束需要切断 $\infty$ 容量的边，不可能是最优解。

理论 + 代码

二分图判定

#include <vector>
using namespace std;

const int MAXN = 100006;
vector<int> adj[MAXN];
int color[MAXN]; // 0=未染, 1=白, 2=黑

bool dfs(int u, int c) {
    color[u] = c;
    for (int v : adj[u]) {
        if (color[v] == 0) {          // ① 未染色，染相反色
            if (!dfs(v, 3 - c)) return false;
        } else if (color[v] == c) {   // ② 同色 → 不是二分图
            return false;
        }
    }
    return true;
}

bool is_bipartite(int N) {
    for (int i = 1; i <= N; i++)
        if (color[i] == 0 && !dfs(i, 1)) return false;
    return true;
}

逐行解析：

• ① 3 - c 把 1 变 2、2 变 1——邻居染相反色。
• ② 如果相邻节点颜色相同，说明存在奇环——不是二分图。

二分图最大匹配（匈牙利算法）

#include <cstring>
using namespace std;

int match[MAXN]; // match[v] = 与 v 配对的左节点，0 表示未配对
bool used[MAXN];

bool dfs_match(int u) {
    for (int v : adj[u]) {
        if (used[v]) continue;
        used[v] = true;
        if (match[v] == 0 || dfs_match(match[v])) { // ① 尝试"让座"
            match[v] = u;
            return true;
        }
    }
    return false;
}

int hungarian(int N) {
    int result = 0;
    for (int u = 1; u <= N; u++) {
        memset(used, false, sizeof(used));
        if (dfs_match(u)) result++;
    }
    return result;
}

逐行解析：

• ① “让座”策略：如果 $v$ 已经配对了（match[v] != 0），尝试让 $v$ 的当前配对对象去找别的配对（递归 dfs_match(match[v])）。如果让座成功，$u$ 就可以和 $v$ 配对。

最大流（Ford-Fulkerson + BFS = Edmonds-Karp）

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

typedef long long ll;
const ll INF = 1e18;
const int MAXN = 506;
struct Edge { int to, rev; ll cap; };
vector<Edge> adj[MAXN];

void add_edge(int u, int v, ll c) {
    adj[u].push_back({v, (int)adj[v].size(), c});      // ① 正向边
    adj[v].push_back({u, (int)adj[u].size() - 1, 0});  // ② 反向边（初始容量 0）
}

ll dfs_flow(int u, int t, ll f, bool visited[]) {
    if (u == t) return f;
    visited[u] = true;
    for (auto& e : adj[u]) {
        if (!visited[e.to] && e.cap > 0) {
            ll d = dfs_flow(e.to, t, min(f, e.cap), visited);
            if (d > 0) {
                e.cap -= d;              // ③ 正向边减少
                adj[e.to][e.rev].cap += d; // ④ 反向边增加（允许撤回）
                return d;
            }
        }
    }
    return 0;
}

ll max_flow(int s, int t) {
    ll total = 0;
    while (true) {
        bool visited[MAXN] = {};
        ll f = dfs_flow(s, t, INF, visited);
        if (f == 0) break;
        total += f;
    }
    return total;
}

逐行解析：

• ①② 每条边同时创建正向边和反向边。反向边初始容量为 0——它不贡献初始流量，但允许后续”撤回”已流的量。
• ③④ 找到增广路后，正向边减少 $d$（用掉了），反向边增加 $d$（允许将来撤回）。这就是”残余图”的核心操作。

例题

例题 1：M&A 047 — Bipartite Graph

题目：$N$ 个顶点 $M$ 条边的无向图。判断是否是二分图。是输出 Yes，否则 No。

数据范围：$1 \le N, M \le 2 \times 10^5$

—— AtCoder M&A 047

分析：BFS 交替染色。从任意节点出发染白色，邻居染黑色，以此类推。如果发现相邻同色则不是二分图。

代码：

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 200006;
vector<int> adj[MAXN];
int color[MAXN];

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    memset(color, -1, sizeof(color));
    bool ok = true;
    for (int s = 1; s <= N && ok; s++) {
        if (color[s] != -1) continue;
        queue<int> q;
        color[s] = 0; q.push(s);
        while (!q.empty() && ok) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (color[v] == -1) {
                    color[v] = 1 - color[u]; // ① 交替染色
                    q.push(v);
                } else if (color[v] == color[u]) {
                    ok = false;               // ② 矛盾
                }
            }
        }
    }
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
}

逐行解析：

• ① 邻居染相反颜色。
• ② 同色邻居出现 = 有奇环 = 不是二分图。

---

例题 2：TB A69 — Bipartite Matching

题目：$N$ 个学生，$N$ 个座位。$C_{i,j}=$ # 表示学生 $i$ 能坐座位 $j$。求最多多少人坐到想要的座位。

数据范围：$1 \le N \le 150$

—— AtCoder Tessoku Book A69

分析：经典二分图最大匹配。左边学生，右边座位。匈牙利算法 DFS 增广。

代码：

#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 156;
char C[MAXN][MAXN];
int matchR[MAXN];
bool visited[MAXN];
int N;

bool dfs(int u) {
    for (int v = 1; v <= N; v++) {
        if (C[u][v] != '#' || visited[v]) continue;
        visited[v] = true;
        if (matchR[v] == 0 || dfs(matchR[v])) { // ① 尝试让出
            matchR[v] = u;
            return true;
        }
    }
    return false;
}

int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            scanf(" %c", &C[i][j]);
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        memset(visited, false, sizeof(visited));
        if (dfs(i)) ans++;                    // ② 每个学生尝试增广
    }
    printf("%d\n", ans);
    return 0;
}

逐行解析：

• ① 如果座位 $v$ 空着，直接匹配。如果被学生 $u'$ 占了，看 $u'$ 能不能换到别的座位（递归）。
• ② 每个学生一轮增广。最坏 $O(N^3)$，但实际很快。

---

例题 3：TB A68 — Maximum Flow

题目：$N$ 个水箱，$M$ 根单向管道。管道 $j$ 从 $A_j$ 到 $B_j$，容量 $C_j$。求从水箱 1 到水箱 $N$ 的最大流量。

数据范围：$2 \le N \le 400$，$1 \le M \le 400$，$0 \le C_j \le 5000$

—— AtCoder Tessoku Book A68

分析：Dinic 最大流模板题。$N \le 400, M \le 400$，Dinic 的 $O(V^2 E) = O(400^2 \times 400) = 6.4 \times 10^7$，足够。

代码：

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

struct Edge { int to, rev; int cap; };

struct Dinic {
    vector<vector<Edge>> g;
    vector<int> level, iter;
    int n;
    Dinic(int n) : n(n), g(n+1), level(n+1), iter(n+1) {}
    void add(int a, int b, int c) {
        g[a].push_back({b, (int)g[b].size(), c});
        g[b].push_back({a, (int)g[a].size()-1, 0});
    }
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0; q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto& e : g[u])
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
        }
        return level[t] >= 0;
    }
    int dfs(int u, int t, int f) {
        if (u == t) return f;
        for (int& i = iter[u]; i < (int)g[u].size(); i++) {
            Edge& e = g[u][i];
            if (e.cap > 0 && level[u] < level[e.to]) {
                int d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    int max_flow(int s, int t) {
        int flow = 0;
        while (bfs(s, t)) {
            fill(iter.begin(), iter.end(), 0);
            int d;
            while ((d = dfs(s, t, 1e9)) > 0) flow += d;
        }
        return flow;
    }
};

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    Dinic dinic(N);
    for (int i = 0; i < M; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        dinic.add(a, b, c); // ① 有向边
    }
    printf("%d\n", dinic.max_flow(1, N));
    return 0;
}

逐行解析：

• ① 注意是单向管道，只加一条有向边（add 函数内部自动创建反向边用于算法）。

验证样例 1：$N=6, M=7$，答案 8。Dinic 会找到多条增广路，最终总流量 8。✓

---

例题 4：ACL Practice D — Maxflow

题目：$N$ 个顶点 $M$ 条边的有向图。求从顶点 0 到顶点 $N-1$ 的最大流。顶点编号 0 开始。

—— AtCoder ACL Practice D

分析：标准最大流模板。Ford-Fulkerson 反复找增广路。注意顶点编号从 0 开始。

代码：

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int MAXN = 206;
struct Edge { int to, rev; ll cap; };
vector<Edge> adj[MAXN];
bool visited[MAXN];

void add_edge(int u, int v, ll c) {
    adj[u].push_back({v, (int)adj[v].size(), c});      // ① 正向边
    adj[v].push_back({u, (int)adj[u].size() - 1, 0});  // ② 反向边容量 0
}

ll dfs_flow(int u, int t, ll f) {
    if (u == t) return f;
    visited[u] = true;
    for (auto& e : adj[u]) {
        if (!visited[e.to] && e.cap > 0) {
            ll d = dfs_flow(e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;                  // ③ 正向减少
                adj[e.to][e.rev].cap += d;   // ④ 反向增加
                return d;
            }
        }
    }
    return 0;
}

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; i++) {
        int a, b; ll c;
        scanf("%d%d%lld", &a, &b, &c);
        add_edge(a, b, c);
    }
    ll total = 0;
    while (true) {
        memset(visited, false, sizeof(visited));
        ll f = dfs_flow(0, N - 1, INF);  // ⑤ 找增广路
        if (f == 0) break;
        total += f;
    }
    printf("%lld\n", total);
}

逐行解析：

• ①② 每条边同时建正向和反向。反向边初始容量 0，允许后续撤回。
• ③④ 增广路找到后，正向边扣掉流量，反向边加上等量——这是 Ford-Fulkerson 的核心操作。
• ⑤ 从源点 0 到汇点 N-1 找增广路。找不到时终止。

参考文献

理论讲义 — AtCoder Algorithm Lectures

• グラフ理論用語集（二部グラフ、マッチング、彩色数 定义）

教材讲解 — 競技プログラミングの鉄則 第 9 章

• 9.8 最大流（B68 ALGO Express = 最小割建模 解说）
• 9.9 二分图匹配（B69 Black Company 2 = 排班建模 解说）

基础练习 — アルゴリズムと数学 演習問題集

• 047 Bipartite Graph（二分图判定）【例题】

系统练习 — 競技プログラミングの鉄則

• A68 Maximum Flow（Dinic 最大流）【例题】
• A69 Bipartite Matching（匈牙利匹配）【例题】

模板练习 — ACL Practice Contest

• D Maxflow（最大流模板）【例题】
• E MinCostFlow（最小费用流）

实战练习 — 競プロ典型 90 問

• 077 Planes on a 2D Plane（★7，二分图匹配+坐标映射）

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化