二分图最大匹配几乎是每个搞竞赛的人都要翻过的一座山而提到最大匹配大多数人的第一反应就是匈牙利算法。ssl1338这道「人员分配」题目名朴素得几乎没什么存在感但它一直在各种刷题列表里被当作二分图最大匹配的模板题反复推荐给两组人、给一些可以配对的组合关系问最多能组成多少对。它的价值不在于题目本身有多难而在于它把二分图建模、最大匹配概念、匈牙利算法的递归实现完整地串了一遍。不管你是刚开始学图论的新手还是想快速拿一个可靠板子的老选手这道题都值得仔细走一遍。1. 从人员分配看二分图建模题面到底在说什么1.1 把题面翻译成图论语言「人员分配」这题的描述一般长这样有一群人被分在两个不同的小组里小组之间会给出若干对“可以合作”的关系小组内部不组队每个人最多只能参与一个组合求最多能组成多少个有效组合。翻译成图论就是三句话两个小组分别作为二分图的左部点和右部点每条“可以合作”的关系就是一条从左部点连向右部点的边每个人只能参与一个组合等价于匹配的定义选出的一组边任何两条没有公共端点。于是“最多能组成多少组合”就变成了“这个二分图的最大匹配数是多少”。这一步建模是整个题目的起点也是最值得反复训练的地方。后面很多匹配题题目包装五花八门拆开之后几乎都是同一个模型。我自己见过不少人拿到题就开始枚举配对方案枚举到一半发现情况越来越多最后把自己绕晕。其实只要在图论模型里把“人员”和“关系”对号入座问题就立刻清晰了。这也是为什么老师总说建模比算法更重要先有模型再有算法顺序不能反。1.2 为什么这类分配问题天然是二分图它天然是二分图的原因很直接约束条件是“组内不能合作”也就是说所有有效边都只存在于两个小组之间组内没有边。这正好是二分图的定义——顶点可以分成两个集合所有边都连接这两个集合。这里要提醒一个常见误区如果题目没有告诉你“分成两组”而是只给N个人和M条关系让你判断能不能做最大匹配那就得先染色判断这个图是不是二分图。做法是任选一个点开始BFS或DFS把它染成黑色把所有邻居染成白色遇到已经有颜色的点就看颜色是否冲突冲突说明存在奇环那就不是二分图匈牙利算法不能直接用得上带花树。模板题之所以叫模板题就是帮你把这一步“判断”省了直接告诉你两组成员。顺带说一句很多人会把“二分图”和“两组人”等价起来这没错但要意识到二分图的本质是“不存在奇环”。只要图中没有奇数长度的环哪怕题目没有分组表述它也依然是二分图照样可以用匈牙利算法。反过来如果关系图里出现了奇环那配对问题就变成了普通图的最大匹配难度完全不在一个量级。1.3 面对模板题先做哪三件事我面对这类题的习惯是先在草稿纸上做三件事而不是急着敲代码。第一明确左部点、右部点的编号范围。模板里一般用 1..n 表示左部点、1..m 表示右部点但题目给出的编号可能是混在一起的需要看清哪些编号属于哪一组。第二确定边的方向。匈牙利算法适合单向建图也就是从左部点连向右部点。如果题目给的是“某人和某人能合作”x 可能来自左部也可能来自右部建图时要先分类再连边。第三确认答案的语义。题目问的是“最多组数”“最少覆盖”还是“能不能全部匹配”语义不同代码出口完全不一样。模板题通常直接问最多组数但读题时还是养成确认的习惯最稳。这三件事做完再写代码就是水到渠成。训练的时候我宁愿多花五分钟想清楚也不边想边写否则后期改起来非常痛苦尤其在考场上时间就是这么省出来的。2. 匈牙利算法的增广路原理让位与递归的真相2.1 匹配、交替路和增广路匈牙利算法建立在三个基础概念上。匹配是一组不含公共端点的边。人员分配里每组成一对就是一个匹配。交替路是从任意一个未匹配点出发依次交替经过非匹配边、匹配边、非匹配边、匹配边……如果最后走到另一个未匹配点这条交替路就叫增广路。增广路有一个非常漂亮的性质路径上非匹配边一定比匹配边多一条。比如一条长度 5 的增广路非匹配边 3 条匹配边 2 条。把这条路上所有边“取反”——匹配边改成非匹配边非匹配边改成匹配边——会让整个匹配的边数加 1。这个操作直观上就是把一路上的座位全部换一遍最终多坐一个人。图论里有一条经典结论一个匹配是最大匹配当且仅当图中不存在增广路。所以匈牙利算法的本质就是一个循环反复寻找增广路找到就匹配数加 1直到找不出来为止。整个算法没有任何玄学就是把“找增广路”这件事用 DFS 高效地做到极致。2.2 用让位逻辑理解递归抽象概念看三遍不如一个具体例子。我把左部点想象成来图书馆的同学右部点想象成座位边表示“这位同学愿意坐这个座位”。现在按编号安排1 号同学看中座位 A坐下2 号同学也看中座位 A但他不能同时坐。2 号尝试让 1 号换到别的愿意坐的座位如果 1 号换到了空座位 B那么 1 号让出 A2 号坐下 A1 号坐 B匹配数从 1 变成 2。如果 1 号愿意坐的座位都有人1 号也可以继续让位让占着那些座位的人再去找新位置这就形成了一条递归的让位链。让位链走到头必然落在一个空座位上链条收束。把链条上所有“座位”置换一遍多出来的位置就是新增的匹配。代码里的递归方式完全复刻了这个过程dfs(u) 检查 u 所有愿意坐的座位 v如果 v 没人坐直接坐如果 v 有人坐就递归地问那个人能不能腾位置。这个类比看起来简单但几乎涵盖匈牙利算法的全部核心。理解了“让位”你再看任何匈牙利代码都会觉得是一回事检查相邻点有空位就占没空位就让匹配者递归去找。2.3 visited 数组就是防止死循环的保险丝很多初学者不理解为什么非要有 used 数组明明已经递归了为什么还要记录“访问过”原因在于让位链上可能出现环。设想u1 想占 v1v1 匹配的是 u2u2 想占 v2v2 匹配的是 u3u3 又想占 v1。如果没有任何记忆dfs 会在 u3 这里再次走到 v1然后继续问 u1……循环往复程序直接栈溢出或者超时。used[v] 的作用是告诉递归函数“v 这个右部点本轮已经试过了不要再试第二次。”因为每一轮搜索中如果 v 曾经尝试失败说明当前状态下达不到空位重复尝试只会走同样的路。于是遇到 used[v]true 直接剪枝跳过。需要注意used 是“每轮”的现场标记不是全局的永久标记。每轮外层循环开始前都要清空这看起来像是细节实则是最容易出 bug 的地方之一下一节专门讲。3. 模板代码逐行拆解一份能直接 AC 的 C 板子3.1 完整代码模板题最好的学习方式是边看边抄边改。先给一份可以省事的 C 板子注释里已经把关键点标好。#include bits/stdc.h using namespace std; const int MAXN 505; int match[MAXN]; // match[v] u右部点 v 当前匹配的是左部点 u0 表示未匹配 vectorint g[MAXN]; // g[u]左部点 u 可以连到的右部点编号集合 bool used[MAXN]; // 本轮 DFS 中右部点 v 是否已经被访问 bool dfs(int u) { for (int v : g[u]) { if (used[v]) continue; // v 本轮已经尝试过跳过 used[v] true; // 标记 v防止递归中出现环 if (match[v] 0 || dfs(match[v])) { match[v] u; // v 空着直接占用或者 v 原来的人腾出位置 return true; } } return false; // u 的所有相邻点都尝试失败 } int main() { int n, m, k; while (cin n m k) { // 多组数据直到文件尾 for (int i 1; i n; i) g[i].clear(); memset(match, 0, sizeof(match)); for (int i 0; i k; i) { int x, y; cin x y; g[x].push_back(y); // 左部点 x 可连接右部点 y } int ans 0; for (int u 1; u n; u) { memset(used, 0, sizeof(used)); // 每轮重新清空 used if (dfs(u)) ans; } cout ans \n; } return 0; }这份代码的输入约定是第一行三个数 n、m、k分别代表左部点数量、右部点数量、关系数量接下来 k 行每行一个关系 (x, y)表示左部点 x 可以和右部点 y 配对。编号统一从 1 开始。如果你手头的题目编号从 0 开始把循环边界和 match 的哨兵值对应调整即可后面会专门讲。3.2 关键行的意图逐个说先看 dfs 函数里的核心判断if (match[v] 0 || dfs(match[v]))match[v]0 表示右部点 v 目前没配对那 u 直接坐上去就行match[v]!0 表示 v 已经被某个左部点占着这个左部点的编号就是 match[v]现在把旧占位者递归地赶去别处。如果 dfs(match[v]) 返回 true说明旧占位者找到了新座位那么 v 就空出来给 u如果返回 false说明旧占位者无路可去v 不能让。这里有个容易绕晕的点递归调用 dfs(match[v]) 成功后match[v] 已经在递归内部被更新成了旧占位者的新座位。回到外层后直接执行 match[v]u 覆盖成当前点逻辑上是“先把 v 让出来再让 u 坐进去”。再看为什么不需要反向边。匈牙利算法的单向建图够用是因为“从右部点回到左部点”这件事根本不需要边只需要 match 数组。match[v] 直接告诉我当前占着 v 的左部点是谁递归就能顺着这个线索往前追溯。第一次接触匈牙利的人常觉得应该存一个反向邻接表其实完全不用。主循环的 for u 1..n是对每个左部点做一次增广尝试。每尝试成功一次匹配数增加 1。别担心尝试顺序会不会影响结果最终只要不存在增广路匹配就是最大匹配顺序不影响最大值只影响具体的配对方案。3.3 手把手模拟一次完整增广我拿一个小例子走一遍。左部点 1、2、3右部点 A、B、C关系为1-A、1-B、2-A、2-C、3-C。第一步u1dfs(1) 先看 AA 空着直接 match[A]1ans1。第二步u2dfs(2) 先看 AA 被 1 占着于是 used[A]true递归 dfs(1)。dfs(1) 再看它所有相邻点A 已被标记跳过B 空着match[B]1返回 true。回到 dfs(2) 后match[A]2ans2。此时匹配是 1-B、2-A。第三步u3dfs(3) 先看 CC 空着match[C]3ans3。最终答案是 3。如果不做第二步的让位1 号就会霸占 A2 号只能选 C3 号没位置答案只有 2。这就是增广路的威力每次让位都让总匹配数加 1。纸上跑完这三步你对匈牙利算法的直观理解会远超看十遍代码。4. 模板题也会翻车初始化、visited 与多组数据的三座大山4.1 多组数据的清空顺序ssl1338 这类模板题经常以多组数据形式给出输入可能包含多个测试用例第一行三个数 n、m、k读到文件尾结束。多组数据最坑的不是算法而是清空。我见过的典型翻车邻接表 g 没有 clear上一组数据的关系全部残留导致 dfs 多出很多“幽灵边”答案莫名偏大match 没有归零上一组的匹配关系残留这一组从一开始就不是空匹配找增广路的结果完全失真used 因为每轮都会 memset反而相对安全但如果外层循环写得有误也会出问题。所以我的习惯是进入 while 循环后第一步永远先清 g 和 match再读边。如果你发现自己改了清空顺序后答案变化了往往不是运气问题而是依赖了上一次数据留下的脏状态。多组数据的调试建议是每组输入结束后打印一下当前组的 match 数组和 ans对比样例输出很容易定位是清空漏了还是逻辑错了。4.2 used 数组的两个错误用法第一个错误是忘了在外层循环清空 used。表现是答案忽大忽小或者换一种输入顺序得到不同结果。因为上一轮搜索中某些右部点被标记成 used这一轮直接跳过导致本可以走的增广边被切断了。第二个错误是试图“聪明地”让 used 跨轮复用。有人觉得“这个右部点反正试过了以后都不用试了”于是一轮 memset 都不写。这是错的。used 表达的是“本轮现场中该右部点已经被考虑过”下一轮现场完全变化新的左部点可能带来完全不同的路径之前失败的右部点可能在新路径中成功。我建议永远按规矩来for (int u 1; u n; u) { memset(used, 0, sizeof(used)); if (dfs(u)) ans; }不要试图省这一行。匈牙利算法的常数本来就不高多一次清空对性能影响微乎其微但能帮你避开一整类难排查的 bug。4.3 match 哨兵值和编号体系要统一match 数组是匈牙利算法最容易初始化错的地方。两种约定都成立点编号从 1 开始match[v]0 表示未匹配初始化用 memset(match, 0, sizeof(match))点编号从 0 开始match[v]-1 表示未匹配初始化用 memset(match, -1, sizeof(match))。最怕混用。读入的编号如果从 0 开始却用 0 作哨兵那么右部点 0 会被误判成“未匹配”接着 dfs(match[v]) 会传入 0 去访问 g[0]可能访问到一坨未初始化的数据最终答案和运行结果都无法预料。我自己的习惯是读入后把左部点和右部点编号统一加 1让所有编号从 1 开始然后用 0 做未匹配哨兵。这样做的好处是 vector 下标和 match 数组语义都非常直观排查问题时少一层转换。如果你写题时发现答案很离谱先别怀疑算法检查一下编号体系和哨兵值是不是统一了。4.4 答案差 1 不是终极原因还有一类同学会在输出前加个 ans1理由是“我样例跑出来总是少一个”。这个操作非常危险ans1 可能恰好蒙对某个样例但绝对掩盖了真实 bug。答案差 1 通常来自三个位置外层循环没有遍历到全部左部点比如循环写成 u n 而不是 u n漏掉最后一个n 的实际含义搞混了循环上限用了右部点数而不是左部点数used 清空时机错了导致某个左部点的增广尝试莫名失败。正确做法是每次输出前用肉眼核对一次样例的匹配过程打印 match 数组看看每个右部点对应到了哪个左部点然后对照预想答案再决定要不要改代码。模板题的数据量小这种打印式调试完全可行而且比凭空猜更快。5. 掌握模板之后从最大匹配延伸出去的三个方向5.1 最小点覆盖选最少的人覆盖所有关系学会了最大匹配第一件能顺手做的事就是最小点覆盖。问题场景依然有一堆可合作关系但现在要挑出几名“负责人”要求每条合作关系至少有一名负责人参与问最少挑几人。在二分图中这个最少人数恰好等于最大匹配数。这是二分图上一个非常经典的点覆盖结论证明思路通常是从最大匹配的一端出发沿着交替路径构造覆盖集。怎么直观理解匹配边两两不共享端点所以每条匹配边都需要至少一个新的覆盖点覆盖数不可能小于匹配数反过来利用最大匹配的交替路径可以构造出规模恰好等于匹配数的覆盖集。在人员分配里应用很直观想用最少人盯住所有合作项目答案就是最大匹配数。这个结论一旦熟记很多看似是“覆盖”的题本质还是先求匹配。5.2 最大独立集选最多的人避免冲突换一个约束“有些人不愿意同组最多能选出多少人组成一个没有合作关系的团队”这就是最大独立集问题二分图上答案是总点数减去最大匹配数。推导链是最大独立集加上最小点覆盖等于总点数因为一个点集是独立集当且仅当它的补集是覆盖集。所以最大独立集等于总点数减去最小点覆盖也就等于总点数减去最大匹配数。排班、社团选人、课程安排这些场景里这个模型很常见。初学阶段可以自己构造一个小数据算完最大匹配和总点数后再把选出的独立集画出来验证。能自己验证一遍比看上十遍结论都牢靠。5.3 数据变大以后怎么办匈牙利算法时间复杂度是 O(VE)边数多的时候不够看。模板题里 n 通常只有几百最多上千跑起来毫无压力。可如果点规模到几万甚至几十万就必须换 Hopcroft-Karp 算法同样是增广路思路但用 BFS 对整张图分层一次找多条互不相交的最短增广路再统一增广复杂度降到 O(E√V)。不过我不建议初学者一上来就啃 HK。HK 代码细节多边界条件复杂没有扎实的匈牙利基础很难一次写对。正确顺序是先用匈牙利把模板题吃透理解增广路的语义再去看 HK 的 BFS 分层和 DFS 多路增广会发现它就是匈牙利在大数据下的优化形态。另外如果有一天你要把这道模板题里的模型用到真实项目里比如做任务分配、排班系统记得不要把编号、左右点数量写死在代码里。把这些参数抽成配置接口匈牙利核心逻辑封装成一个函数输入是邻接表和两侧点数输出是最大匹配数和具体配对方案。这样你在新场景里复用的时候只需要改数据输入算法部分一行都不用动。最后说一个我当年训练时被反复叮嘱的小技巧刷模板题不能只看代码能不能跑通样例。我会在草稿纸上把样例的每一条增广路都画出来标出哪些边是匹配边、哪些是非匹配边然后对照代码的递归过程一步步看 used 标记和 match 更新发生在哪里。这套功夫花不了多少时间但对理解匈牙利算法的帮助比刷十道难题都大。如果你是自己学也建议把这份代码存成自己的模板文件在每道匹配题里都拿出来改一改用顺手之后你会发现“会背模板”和“懂模板”之间差的其实就是这张草稿纸上的几张图。