【解雨臣的算法课】第四课：二分图与匈牙利算法——最优配对，谁也不落空
“下斗组队，最怕的就是有人闲着，有人累死。好的领队，得把活儿分明白。”
——解雨臣
一、上节课回顾
上一课我们讲了前缀和与差分——用空间换时间，提前算好别现算。
胖子用差分算了一回机关次数，十分钟就搞定了，而之前他打算一个一个格子去数。
胖子：“原来提前算好这么爽！”
黑瞎子：“那当然，这叫预处理。”
胖子：“那我以后啥都先算一遍。”
我：“你内存够吗？”
今天我们讲一个配对的利器——二分图与匈牙利算法。
二、故事引入：解雨臣分任务
有一次下斗，我们仨遇到了一排机关。
有 n 个机关，每个机关只能由特定的人解开：
- 解雨臣：能解机关 1、2、3
- 黑瞎子：能解机关 2、4
- 王胖子：能解机关 3、5
每个机关只需要一个人解，每个人最多解一个机关。
问：最多能解开几个机关？
胖子说：“这简单！我先挑最难的解，剩下的你们分。”
黑瞎子说：“你那个算法不行，万一你抢了别人的关键机关呢？”
我说：“这就是二分图最大匹配问题。”
三、什么是二分图？
3.1 定义
二分图：图中的点可以分成两个集合 U 和 V，使得所有边都连接 U 和 V 之间的点，集合内部没有边。
U集合（人） V集合（机关）
解雨臣 ──────── 机关1
──────── 机关2
──────── 机关3
黑瞎子 ──────── 机关2
──────── 机关4
王胖子 ──────── 机关3
──────── 机关5
3.2 二分图的判定
一个图是二分图 \iff 可以用两种颜色染色，使得相邻点颜色不同。
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int m;
vector <int> g[N];
int color[N];
bool dfs (int u, int c)
{
color[u] = c;
for (int v : g[u])
{
if (color[v] == c)
{
return false;
}
if (color[v] == 0 && !dfs (v, 3 - c))
{
return false;
}
}
return true;
}
四、什么是匹配？
4.1 基本概念
匹配：一组边，其中任意两条边没有公共顶点。
最大匹配：边数最多的匹配。
完美匹配：所有顶点都被匹配。
4.2 例子
初始：所有点未匹配
匹配1：解雨臣-机关1，黑瞎子-机关2 → 2条边（不是最大）
匹配2：解雨臣-机关2，黑瞎子-机关4，胖子-机关3 → 3条边（最大）
五、匈牙利算法
5.1 算法思想
核心思想：尝试给每个左部点找对象，如果冲突了，就让已经匹配的点尝试换一个。
解雨臣说：“这就像相亲——你先约一个，如果对方已经被约了，就让那个男生换个女生，腾出位置给你。”
5.2 算法步骤
- 遍历左部每个点 u
- 对 u 尝试匹配：
- 遍历 u 的所有邻居 v
- 如果 v 没匹配，直接匹配
- 如果 v 已匹配，尝试让匹配 v 的点 match[v] 重新匹配（DFS）
- 如果找到增广路，匹配数 +1
5.3 代码模板
#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n1;
int n2;
int m;
vector <int> g[N];
int match[N];
bool vis[N];
bool dfs (int u)
{
for (int v : g[u])
{
if (vis[v])
{
continue;
}
vis[v] = true;
if (match[v] == 0 || dfs (match[v]))
{
match[v] = u;
return true;
}
}
return false;
}
int main ()
{
cin >> n1 >> n2 >> m;
for (int i = 1; i <= m; i++)
{
int u;
int v;
cin >> u >> v;
g[u].push_back (v);
}
int ans = 0;
for (int i = 1; i <= n1; i++)
{
memset (vis, 0, sizeof (vis));
if (dfs (i))
{
ans++;
}
}
cout << ans << endl;
return 0;
}
5.4 复杂度分析
- 每次 DFS 最坏 O(E)
- 总共 n_1 次 DFS
- 总复杂度：O(n_1 \times E)
- 邻接表实现，实际运行很快
六、经典例题：解雨臣的相亲大会
题目背景
解家要办相亲大会，有 n 个男生和 m 个女生。
每个男生有一个心仪女生列表。
每个女生只能和一个男生配对。
问：最多能配对多少对？
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
int m;
int k;
vector <int> g[N];
int match[N];
bool vis[N];
bool dfs (int u)
{
for (int v : g[u])
{
if (vis[v])
{
continue;
}
vis[v] = true;
if (match[v] == 0 || dfs (match[v]))
{
match[v] = u;
return true;
}
}
return false;
}
int main ()
{
cin >> n >> m >> k;
for (int i = 1; i <= k; i++)
{
int u;
int v;
cin >> u >> v;
g[u].push_back (v);
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
memset (vis, 0, sizeof (vis));
if (dfs (i))
{
ans++;
}
}
cout << ans << endl;
return 0;
}
七、经典例题2：解雨臣的棋盘覆盖
题目背景
有一个 n \times n 的棋盘，某些格子有障碍物。
要用 1 \times 2 的多米诺骨牌覆盖棋盘（骨牌可以横着放或竖着放）。
问：最多能放多少块骨牌？
思路分析
关键转化：棋盘黑白染色！
- 把棋盘按 (i+j) 的奇偶性分成黑格和白格
- 每块骨牌必然覆盖一个黑格和一个白格
- 这就变成了二分图匹配问题：
- 左部：黑格
- 右部：白格
- 相邻的格子连边（上下左右）
- 最大匹配数 = 最多骨牌数
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n;
int m;
bool block[N][N];
int id[N][N];
vector <int> g[N * N];
int match[N * N];
bool vis[N * N];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
bool dfs (int u)
{
for (int v : g[u])
{
if (vis[v])
{
continue;
}
vis[v] = true;
if (match[v] == 0 || dfs (match[v]))
{
match[v] = u;
return true;
}
}
return false;
}
int main ()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x;
int y;
cin >> x >> y;
block[x][y] = true;
}
int cnt = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (!block[i][j])
{
id[i][j] = ++cnt;
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (block[i][j] || (i + j) % 2 == 0)
{
continue;
}
int u = id[i][j];
for (int k = 0; k < 4; k++)
{
int x = i + dx[k];
int y = j + dy[k];
if (x >= 1 && x <= n && y >= 1 && y <= n && !block[x][y])
{
int v = id[x][y];
g[u].push_back (v);
}
}
}
}
int ans = 0;
for (int i = 1; i <= cnt; i++)
{
memset (vis, 0, sizeof (vis));
if (dfs (i))
{
ans++;
}
}
cout << ans << endl;
return 0;
}
八、二分图的其他应用
| 问题类型 | 转化方法 |
|---|---|
| 最大匹配 | 匈牙利算法 |
| 最小点覆盖 | 最大匹配 = 最小点覆盖（König定理） |
| 最大独立集 | 总点数 - 最小点覆盖 |
| 最小路径覆盖 | 总点数 - 最大匹配（DAG） |
| 棋盘覆盖 | 黑白染色转二分图 |
König定理
在二分图中，最大匹配数 = 最小点覆盖数
最小点覆盖：选最少的点，使得所有边至少有一个端点被选。
最大独立集：选最多的点，使得任意两点之间没有边。
$$\text{最大独立集} = \text{总点数} - \text{最小点覆盖} = \text{总点数} - \text{最大匹配}$$
九、解雨臣踩过的坑
坑1：vis 数组每轮重置
// 错误：vis 只重置一次
bool vis[N];
for (int i = 1; i <= n1; i++)
{
dfs(i); // 第二次 dfs 时 vis 还是 true
}
// 正确：每轮重置
for (int i = 1; i <= n1; i++)
{
memset(vis, 0, sizeof(vis));
dfs(i);
}
解家箴言：vis 标记的是本轮尝试中访问过的右部点，每轮都要重置。
坑2：match 数组含义混淆
match[v] = u; // v是右部点，u是左部点
解家箴言：统一方向，别混了。通常 match[右部点] = 左部点。
坑3：图不是二分图
匈牙利算法只适用于二分图。如果不是二分图，需要其他算法（如带花树）。
解家箴言：先用染色法确认是不是二分图。
坑4：左右部点数不对称
// 只从左部出发
for (int i = 1; i <= n1; i++)
{
dfs(i);
}
解家箴言：只遍历左部点，右部点不主动发起匹配。
十、课后习题（解家的考验）
基础题
-
最大匹配：给定二分图，求最大匹配数。（直接套模板）
-
课程表：有 n 门课，m 个老师。每门课需要一个老师，每个老师最多教一门课。已知每个老师能教的课程列表，求最多能开多少门课。
进阶题
-
解雨臣的保镖：有 n 个任务和 m 个保镖。每个保镖只能保护特定的一些任务。但有个限制：如果一个保镖被分配了任务，他旁边的保镖（编号相邻）就不能再分配任务。求最多能完成多少任务。（提示：把保镖按奇偶分成两组）
-
棋盘放置：在 n \times n 的棋盘上放车（象棋里的车），要求它们互不攻击。某些格子不能放。求最多能放多少个车。（提示：每行每列最多一个，行和列建二分图）
挑战题（来自青铜门的考验）
- 解雨臣的密码锁：有一个 n \times m 的密码盘，每个格子是 0 或 1。每次操作可以翻转一行或一列的所有格子。问能否通过若干次操作，让所有格子都变成 0？如果能，最少需要多少次操作？
提示：设 x_i 表示第 i 行是否翻转，y_j 表示第 j 列是否翻转。每个格子 (i,j) 的最终值是 a_{i,j} \oplus x_i \oplus y_j。要让它等于 0，即 x_i \oplus y_j = a_{i,j}。这就变成了二分图染色问题。
十一、下集预告
“匹配就像下斗组队——每个人都有自己的特长，得找到最合适的搭档，才能发挥最大作用。”
——解雨臣
下一课，最短路算法——如何在墓室里找到最快的逃生路线。
胖子总爱乱跑，每次都找不到出口。学了这课，他就能自己找到路了。
下课。
（本系列课程由解雨臣独家赞助，信友队论坛首发。转载需注明出处。）