InoueMoby's Blog

前言

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

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

这个问题看似和图遍历无关，但它的求解方法——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$ （城市）。流要满足：

每条边上的流量 $\le$ 容量
除 $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 \times M$ 的网格，有些格子有障碍物（#），其余为空（.）。用 $1 \times 2$ 的骨牌覆盖空格子（横放或竖放），骨牌不能重叠。最多放多少块？并输出一种方案。

数据范围： $1 \le N, M \le 100$

—— AtCoder ACL Practice D

分析：经典二分图匹配。对网格黑白染色，相邻格子颜色不同。把每个空格子看作节点，横/竖相邻的空格子之间连边，构成二分图。最大匹配数 = 最多骨牌数。

用最大流求解：源点连所有黑格子（容量 1），黑格子连相邻白格子（容量 1），白格子连汇点（容量 1）。

代码：

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

const int MAXV = 10010;
const int INF = 1e9;
struct Edge { int to, cap, rev; };
vector<Edge> graph[MAXV];
int level[MAXV], iter[MAXV];

void add_edge(int from, int to, int cap) {
    graph[from].push_back({to, cap, (int)graph[to].size()});
    graph[to].push_back({from, 0, (int)graph[from].size() - 1});
}

bool bfs(int s, int t) {
    memset(level, -1, sizeof(level));
    queue<int> q;
    level[s] = 0; q.push(s);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (auto& e : graph[v])
            if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; q.push(e.to); }
    }
    return level[t] >= 0;
}

int dfs(int v, int t, int f) {
    if (v == t) return f;
    for (int& i = iter[v]; i < (int)graph[v].size(); i++) {
        Edge& e = graph[v][i];
        if (e.cap > 0 && level[v] < level[e.to]) {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) { e.cap -= d; graph[e.to][e.rev].cap += d; return d; }
        }
    }
    return 0;
}

int max_flow(int s, int t) {
    int flow = 0;
    while (bfs(s, t)) {
        memset(iter, 0, sizeof(iter));
        int f;
        while ((f = dfs(s, t, INF)) > 0) flow += f;
    }
    return flow;
}

int N, M;
char S[105][105];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
char ans[105][105];

int main() {
    scanf("%d%d", &N, &M);
    for (int i = 0; i < N; i++) scanf("%s", S[i]);
    // ① 建图：黑白染色，源点=NM，汇点=NM+1
    int src = N * M, sink = N * M + 1;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) {
            if (S[i][j] == '#') continue;
            int id = i * M + j;
            if ((i + j) % 2 == 0) {
                add_edge(src, id, 1);          // ② 黑格子连源点
                for (int d = 0; d < 4; d++) {
                    int ni = i + dx[d], nj = j + dy[d];
                    if (ni >= 0 && ni < N && nj >= 0 && nj < M && S[ni][nj] == '.')
                        add_edge(id, ni * M + nj, 1); // ③ 黑连白（四方向）
                }
            } else {
                add_edge(id, sink, 1);         // ④ 白格子连汇点
            }
        }

    int flow = max_flow(src, sink);
    printf("%d\n", flow);

    // ⑤ 还原方案：看哪些边被用了
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) ans[i][j] = S[i][j];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) {
            if ((i + j) % 2 != 0 || S[i][j] == '#') continue;
            int id = i * M + j;
            for (auto& e : graph[id]) {
                if (e.to == src || e.cap > 0) continue; // ⑥ cap=0 说明这条边被用了
                int ni = e.to / M, nj = e.to % M;
                if (ni == i - 1) { ans[i-1][j] = 'v'; ans[i][j] = '^'; } // 上→下
                else if (ni == i + 1) { ans[i][j] = 'v'; ans[i+1][j] = '^'; } // 下→下
                else if (nj == j - 1) { ans[i][j-1] = '>'; ans[i][j] = '<'; } // 左→右
                else if (nj == j + 1) { ans[i][j] = '>'; ans[i][j+1] = '<'; } // 右→右
            }
        }
    for (int i = 0; i < N; i++) printf("%s\n", ans[i]);
}

逐行解析：

①②③④ 将网格建模为二分图：源点连黑格子，黑格子连相邻白格子，白格子连汇点，所有边容量 1。
⑤⑥ 还原方案：遍历黑格子的出边，如果 cap == 0 说明这条边在最大流中被使用了（流量消耗了容量）。根据邻接方向标记 v/^ 或 >/<。

分析：标准最大流模板。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 章

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

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

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

模板练习 — ACL Practice Contest

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

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

系列索引

第零章基础工具

第一章搜索技术

第二章数学基础

第三章数据结构

第四章图论

第五章动态规划

第六章贪心

第七章字符串

第八章进阶

竞技编程 04-07 二分图匹配与最大流

从"二分图染色"到"最大匹配"，再到"最大流最小割"——图论中最美的对偶定理

前言

问题的本质

什么是二分图？

匹配是什么？

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

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

理论 + 代码

二分图判定

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

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

例题

例题 1：M&A 047 — Bipartite Graph

例题 2：TB A69 — Bipartite Matching

例题 3：TB A68 — Maximum Flow

例题 4：ACL Practice D — Maxflow（网格多米诺骨牌）

参考文献

系列索引

竞技编程 04-07 二分图匹配与最大流