搞 ACM 和算法题的人应该都有这种体验很多问题看起来完全不搭边比如“给 N 个学生分配 M 个社团岗位”、“棋盘上放最多的车”、“把一堆任务派给一堆机器”最后扒开外层包装画成图之后全是同一个东西——二分图最大匹配。这个算法不像最短路、最小生成树那样有一堆变体核心就一个匈牙利算法。代码量不大但里面的“增广路”思想一旦没吃透改个题面就懵。这篇文章我会用实战角度把二分图最大匹配的完整套路讲透从概念到模板、从常见坑到扩展结论争取你看完就能直接抄代码去做题。如果你是刚开始学图论的 C 选手这篇文章能帮你把“匹配”这条线一次性理顺如果你已经会写匈牙利重点可以放在第 4 章的优化和常见错误排查上那里有不少我踩过的坑。1. 内容整体设计与思路拆解1.1 先搞清楚二分图是个什么东西二分图Bipartite Graph的定义一句话就能说清把图里的所有顶点分成左右两个集合每条边的两个端点必须一个在左、一个在右也就是说不存在一条边同时连两个左顶点或者同时连两个右顶点。平时判断一个图是不是二分图最常用的办法是染色法。从任意一个点出发给它染成颜色 0相邻的点染成颜色 1再相邻的点又染成颜色 0如果整个过程没出现冲突某个点被要求同时染成 0 和 1那这个图就是二分图。实现上用 BFS 或者 DFS 都行代码量很小。染色法的本质是在检查“图中是否存在奇环”。环长度为奇数的时候绕一圈回来会发现起点被染成了相反颜色必然冲突。这个结论在做题时很有用因为很多题目不会直接告诉你“这是二分图”而是要你先用染色法自己判断判断通过之后才能套匹配算法。1.2 匹配、最大匹配、完美匹配这些词到底在说什么匹配Matching是在图里选一组边要求这些边两两之间没有公共顶点。大白话就是一条边占用了它两端的两个人/两个资源那这两个人被占用了之后不能再参与其他边。匹配的大小就是选了边的条数。最大匹配就是在所有可能的匹配里让边数最多的那个。完美匹配则是另一个概念左集合和右集合顶点数相同并且每条边恰好把左右顶点一一配对一个不剩。这里必须强调一个很容易混淆的点完美匹配一定是最大匹配但最大匹配不一定是完美匹配。更关键的是最大匹配的解不唯一你在写题的时候往往只需要返回匹配数量但有些题目会要求输出具体的匹配方案这时候match[]数组就直接派上用场了后面我会细讲。1.3 增广路匈牙利算法的灵魂如果只记一个东西就记增广路Augmenting Path的概念。增广路是这么一条路径它以某个“没有被匹配的左顶点”为起点交替经过“未匹配边 → 已匹配边 → 未匹配边 → 已匹配边 …”最后停在某个“没有被匹配的右顶点”上。我直接举例。左顶点 a 没有匹配右顶点 x 已经和左顶点 b 匹配了左顶点 b 除了连 x 之外还连了右顶点 y而 y 目前也没匹配。那么从 a 出发走 a→x未匹配边、x→b已匹配边、b→y未匹配边终点 y 是未匹配的。这就是一条增广路。增广路的威力在于你把这条路径上的边“翻转”一下未匹配边变成匹配边已匹配边取消匹配整体匹配数会 1。上面例子里翻转之后a 匹配 xb 匹配 y从原来的 1 条匹配变成 2 条匹配。匈牙利算法的核心逻辑于是变得极其简单不断找增广路找到一条就翻转一条直到找不到为止此时匹配就是最大的。这个结论叫 Berge 定理是整个算法的理论基石。2. 核心细节解析与实操要点2.1 为什么用 DFS 就能找增广路找增广路最直观的写法是 BFS一层一层交替扩展判重后找到终点就停。但实战中最常用的还是 DFS原因有两个一是代码量少二是递归本身自带“回溯”能力天然契合增广路的翻转逻辑。DFS 的思路可以这样理解假设当前要尝试给左顶点 u 找一个匹配对象遍历 u 的所有邻接右顶点 v如果 v 没有被匹配直接用 u 占掉 v返回成功。如果 v 已经被别的左顶点匹配了不要立刻放弃尝试“劝说”那个左顶点match[v]换个别的右顶点。如果match[v]能找到新的对象那 v 就空出来了u 就可以匹配 v。这个过程用递归写出来非常优雅。而且注意一个关键细节我们需要对“右顶点”做访问标记vis[v]防止递归进入死循环。每次尝试给新的左顶点匹配时vis必须清空。这是初学者最容易犯的错误之一很多人把vis放在函数外面用全局结果第二个左顶点开始就匹配错。2.2 核心数据结构match[] 和 vis[]匈牙利算法只需要两个核心数组数组含义初始化match[v]右顶点 v 当前匹配的左顶点编号-1表示未匹配-1vis[v]当前这轮 DFS 里右顶点 v 是否被访问过false每轮清空match[]是全局状态记录的是当前匹配方案的最终结果也是题目让你输出匹配方案时的答案来源。注意它只对右顶点开数组因为在 DFS 里我们需要知道“右顶点 v 被谁占了”至于某个左顶点匹配了谁其实在match[]里已经隐含了不需要单独再开一个left_match[]。vis[]的作用是防止重复访问同一个右顶点。考虑一个场景左顶点 u 连接右顶点 v1v1 被左顶点 a 占用a 又连接 v1、v2v2 被左顶点 b 占用b 又连接 v1……如果不对右顶点做访问标记递归会在 v1 和 v2 之间无限循环。标记为 true 之后同一轮探索里右边的点最多被尝试一次既防止死循环也保证递归层数可控。2.3 复杂度分析为什么匈牙利算法是 O(VE)匈牙利算法的复杂度是 O(VE)V 是全图的顶点数E 是边数。这个复杂度听起来不低但实际运行效果往往比理论上限好很多。一次 DFS 的过程最坏会尝试访问所有边复杂度 O(E)。而最多需要做多少次 DFS理论上每个左顶点都要试一次所以是 O(V)。乘起来就是 O(VE)。这个复杂度的关键特征是它只受“左顶点个数”和“边数”影响不受右顶点个数影响所以实际应用里我们要做的第一件事就是把顶点数量少的那一侧作为左集合。另外很多匹配题目都是稀疏图DFS 实际遍历的边数远小于 E跑起来比理论值快很多。但遇到 1e5 级别的大数据就别硬上匈牙利了改用 Hopcroft-Karp 算法那个是 O(E√V)后面我会给出对比。3. 实操过程与核心环节实现3.1 建图方式选择邻接表是关键匈牙利算法对图的存储方式没有硬性要求但强烈建议用邻接表。很多初学者习惯用邻接矩阵bool edge[N][N]在 1000×1000 的小数据上没问题但面对 5000×5000 的图矩阵光初始化就 2500 万个元素时间和内存都吃不消。邻接表的空间和边的数量成正比稀疏图优势巨大。我用的是链式前向星因为它在多数 ACM 模板里最顺手struct Edge { int to, next; } e[MAXM]; int head[MAXN], idx 0; void addEdge(int u, int v) { e[idx].to v; e[idx].next head[u]; head[u] idx; }注意如果是多组测试数据初始化一定要把head[]全部置成 -1idx置 0。我见过太多人只记得清match[]忘了清head[]结果第二组样例莫名多出旧边匹配数虚高查错查到崩溃。3.2 匈牙利算法 DFS 模板逐行拆解直接给出最核心的 DFS 函数bool dfs(int u) { for (int i head[u]; i ! -1; i e[i].next) { int v e[i].to; if (vis[v]) continue; vis[v] true; if (match[v] -1 || dfs(match[v])) { match[v] u; return true; } } return false; }逐行解释for循环遍历左顶点 u 的所有邻接边。if (vis[v]) continue;v 已经在当前 DFS 中访问过跳过防止死循环。vis[v] true;标记 v 已访问这行必须在递归之前不要放在if外面。if (match[v] -1 || dfs(match[v]))如果 v 空闲或者能劝动 v 的当前主人换个对象就说明 v 可以被 u 拿下。match[v] u;把 v 的匹配对象改成 u这是“翻转”操作的一部分。返回true表示找到了增广路匹配数可以 1。然后主函数int hungarian() { int res 0; memset(match, -1, sizeof(match)); for (int u 1; u n; u) { memset(vis, false, sizeof(vis)); if (dfs(u)) res; } return res; }注意两个细节memset(vis, false, sizeof(vis))在每次循环里都要执行因为每一轮dfs都是独立的一次“找增广路”尝试右顶点在同一轮内的访问状态必须共享但轮与轮之间不能互相影响。递归终点不只是match[v] -1还存在一种情况dfs(match[v])返回 false说明 v 的主人换不了那就跳出递归返回上一层继续尝试 u 的其他邻居。3.3 一个完整可运行的实战例子我做一道典型的二分图匹配题左边是 5 个学生右边是 4 个社团边的含义是“该学生可以参加该社团”求最多能匹配多少个社团。#include bits/stdc.h using namespace std; const int MAXN 1000; struct Edge { int to, next; } e[MAXN * MAXN]; int head[MAXN], idx; int match[MAXN]; bool vis[MAXN]; void init() { idx 0; memset(head, -1, sizeof(head)); } void addEdge(int u, int v) { e[idx].to v; e[idx].next head[u]; head[u] idx; } bool dfs(int u) { for (int i head[u]; i ! -1; i e[i].next) { int v e[i].to; if (vis[v]) continue; vis[v] true; if (match[v] -1 || dfs(match[v])) { match[v] u; return true; } } return false; } int main() { int n 5, m 4; init(); addEdge(1, 1); addEdge(1, 2); addEdge(2, 2); addEdge(2, 3); addEdge(3, 1); addEdge(3, 3); addEdge(4, 4); addEdge(5, 2); memset(match, -1, sizeof(match)); int res 0; for (int u 1; u n; u) { memset(vis, false, sizeof(vis)); if (dfs(u)) res; } printf(最大匹配数: %d\n, res); for (int v 1; v m; v) { if (match[v] ! -1) { printf(学生 %d - 社团 %d\n, match[v], v); } } return 0; }运行结果最大匹配数是 4输出具体的匹配方案能直观看到match[]数组的最终状态。建议你自己动手跑一遍并逐步打印理解递归调用过程这是我觉得记忆最牢固的学习方式。3.4 实战中值得收藏的代码风格细节写匈牙利算法有几处代码风格上的取舍实战中直接影响 debug 效率。第一dfs函数的返回值设计为bool而不是int。我们只关心这轮是否找到增广路不需要它返回路径布尔值语义最清晰。第二把vis[]声明成全局数组但清空用memset。memset对 1000 大小的数组开销极小不要为了省这点时间自己去写for循环清空代码会变得啰嗦。第三递归深度问题。匈牙利算法在最坏情况下递归深度可能达到左顶点数量比如 1e5 个顶点时可能会导致栈溢出。常见的解决办法是在编译选项里加大栈空间或者把 DFS 改成手工栈写法。但大多数竞赛题目左顶点不超过 5000直接用递归问题不大。我之前用 Windows 的 VS Code 写算法题时默认栈不够大遇到 2e4 规模的匹配就爆栈后来改用 Linux 环境或者用#pragma comment(linker, /STACK:1024000000,1024000000)才解决。4. 常见问题与排查技巧实录4.1 最容易踩的 5 个坑我们队实战训练里踩过的坑整理成一张表每一条都是真实遭遇错误现象根本原因解决办法匹配数比实际大清了match[]忘了清head[]旧边残留init()里同时重置head[]和idx第二个左顶点开始匹配失败vis[]在循环里没清空每轮循环memset(vis, false, sizeof(vis))死循环右顶点递归访问互相拉扯vis[v]标记必须放在dfs(match[v])之前递归爆栈顶点数过大递归层数太深换 Hopcroft-Karp 或手工栈答案正确但输出方案不对只输出遍历左顶点的匹配结果按match[v]反向遍历输出右顶点作为下标vis[v]标记位置这个坑我单独展开讲。很多人会写成if (match[v] -1 || dfs(match[v])) { match[v] u; return true; }但把vis[v] true写在if里面会导致递归进去之后另一个方向又把 v 当新点处理路径交错形成环。正确写法是进入循环体立刻标记保证 v 在本轮 DFS 中不被第二次访问。4.2 二分图匹配的四个必背结论最大匹配学的不仅仅是匹配本身它和很多图论概念直接挂钩。这四个结论是我做题时用烂了的最小点覆盖 最大匹配Kőnig 定理。二分图里选出最少的顶点使得每条边至少有一个端点被选中这个最小数量等于最大匹配数。典型题目是“用最少的人看住所有边”。最大独立集 总顶点数 - 最大匹配。选出最多的顶点使得任意两点之间没有边。等价于“删掉最少的点让剩余点互不相连”。最小边覆盖 总顶点数 - 最大匹配。选出最少的边使得每个顶点都至少是某条边的端点。DAG 最小路径覆盖 顶点数 - 对应二分图最大匹配。把有向无环图拆成二分图来求。这四个结论在做“套路题”时几乎是标准答案看到“最少”、“最大”、“覆盖”、“独立”这些词第一反应就要往匹配上靠。4.3 什么时候必须放弃匈牙利算法匈牙利算法不是银弹。虽然大多数题目数据范围在几百到几千但有的题目会直接给到 1e5 甚至 1e6 的规模。比如 N100000、M100000 的二分匹配问题匈牙利算法 O(VE) 就是 1e10 级别机器跑不动。这种时候需要上 Hopcroft-Karp 算法。HK 算法的核心是把 DFS 找单条增广路改成 BFS 分层 DFS 多路增广同时找多条增广路复杂度降到 O(E√V)。代码量比匈牙利多一些但结构也没复杂到像网络流那样。如果你只学一个优化算法HK 是最推荐的匹配进阶算法。另一个选择是用最大流模型把源点连左顶点、左顶点连右顶点、右顶点连汇点所有容量设 1跑 Dinic复杂度也是 O(E√V) 的量级。但 Dinic 的常数比 HK 大而且代码长得多题解一般不会建议这么做除非题目本身已经是网络流形式。4.4 如何快速定位“这不是二分图匹配题”很多题目不会直接写“二分图最大匹配”需要你自己识别转化模型。我总结了一套识别流程题面出现“配对”、“分配”、“选座”、“不能冲突”这类关键词。能画出两个集合边只存在于两集合之间且集合内部没有边。目标是让配对数量最多或者求一种方案使某人/某物不被闲置。染色法验证图是二分图。例如 N 个男生、M 个女生参加舞会男生和女生之间互有好感才能配对棋盘上放若干个“车”使得互相不能吃掉课程安排里每个老师上一门课且同一时间不冲突。全是二分图匹配。反过来如果图内部存在同性别的边或者一个点可以同时连多条同侧边那多半是别的算法不要硬套匈牙利。4.5 调试匈牙利算法的一招制敌法匈牙利算法的 bug 不太容易通过样例发现因为样例数据往往太小。我的调试习惯是构造一个“链式”极限数据左顶点 1 连接到右顶点 1 和 2左顶点 2 连接到右顶点 2左顶点 3 连接到右顶点 1。如果代码没问题最大匹配是 2比如 1→1、2→2或者 3→1、2→2。如果代码有 bug 导致匹配数是 3那明显就是vis[]或match[]维护出错了。再进一步对于无法肉眼验证的复杂数据我通常打印每一轮dfs进去、出来时的u、v、match[]状态用日志对比手算结果。递归函数调试千万别用大样例你根本盯不过来先用最小规模把逻辑验证对再上大数据压时间。5. 扩展应用与进阶方向5.1 带权二分图最大匹配有些题目在“能不能匹配”之外还要求“总权值最大”。这时要换 KM 算法Kuhn-Munkres它专门解决完备匹配中的最大权匹配问题复杂度 O(V³)。KM 适用的前提是左右两侧顶点数相同且要求完备匹配。如果题目允许“不匹配一部分点”通常做法是补虚拟节点把虚拟节点边的权值设为 0。实际比赛里带权匹配题目不多但一旦出现很多人会把匈牙利硬套上去导致答案偏小。这个点需要额外留意。但我必须提醒一点如果边的权值可以是负数KM 的初始化处理会很麻烦建议直接用最小费用最大流模型通用性更强。5.2 多重匹配与延迟匹配有一种变体是一个右顶点可以匹配多个左顶点比如一个社团可以容纳 k 个人。处理方法是把每个右顶点拆成 k 个容量为 1 的节点再跑标准匈牙利。或者直接在 DFS 里给每个右顶点记录剩余容量match[v]改成数组。延迟匹配Deferred Matching则更进阶常见于在线算法或推荐系统核心思想是“先随便匹配后面用增广路调整”。这个思想在真实业务里有广泛应用比如打车平台的订单分配用户来了先分个司机后面发现更优方案再调整。理解匈牙利算法对理解这类业务算法帮助很大。5.3 实际工程里的 C 实现注意事项如果要把二分图匹配用在实际工程比如 C 后端项目里而不是打比赛有几个工程化细节需要处理。一是内存管理。链式前向星在工程里不如vectorint adj[]直观工程上我更喜欢用vectorvectorint代码可读性强即使性能略低也没关系。但要注意vector的清空效率用.clear()不会释放容量多组数据处理时更友好。二是多线程安全性。匈牙利算法的match[]和vis[]都是全局状态如果多个线程同时跑匹配必须加锁或者每个线程独立拷贝状态。工程里更推荐直接复制数据结构再跑匹配对象规模一般不会太大。三是 C 版本选择。写算法题用 C11 就够了但工程里可以享受std::function、lambda 捕获带来的便利。递归 DFS 用 lambda 会导致dfs引用自身时写法比较复杂我一般直接声明成普通成员函数避免用std::function的性能开销。6. 从模板到内化的总结体会最后分享一点我个人的实际感受。匈牙利算法看起来只有十几行但它其实是很多“贪心 反悔”类算法的原型。你写一个左顶点匹配失败时递归去“劝”别人换对象的过程本质上就是一次带回溯的决策。理解了这一点你会突然发现很多看似无关的问题——比如任务分配、倾角匹配、电路板布线、课程表编排——都能用同一套模板秒杀掉。学这个算法我最推荐的三步走手动画一个二分图自己手动执行几轮 dfs把递归调用的过程在纸上画成树形结构。把增广路翻转的过程落实到代码里不要死记模板要能说清楚match[v]为什么这样改。大量刷题重点是识别匹配模型的题目转换过程而不是背代码。如果你的目标是比赛建议同时在本地存一份匈牙利模板和一份 HK 模板按数据范围快速切换。下次再遇到“最大匹配”问题时你就可以直接掏出模板心里不慌。