企业官网建设流程全解析

当年我在刷题榜上看到“ssl1338 人员分配”这道题时，第一反应是松了口气。标题把考点全写在脸上了：二分图、最大匹配、匈牙利算法。但紧接着又有点心虚——越是模板题，越容易在细节上翻车。如果你也背过匈牙利算法的板子，却总在“第几行该清空数组”“match数组到底存的是谁”这种问题上卡壳，那这篇就适合你。我会把这道人员分配题当作引子，从图论建模讲到匈牙利算法的增广路原理，再给出一份可以直接提交的模板代码，最后把考场和实战里最常踩的坑列成一个排查清单。无论你是刚接触二分图匹配的新手，还是准备竞赛复盘的选手，都能从这里拿到能直接用的东西。

1. 这题到底在考什么：把“人员分配”翻译成二分图匹配

1.1 题面背后的一句话

模板题之所以叫模板题，是因为它把算法考点包装得很浅。ssl1338“人员分配”这类题挂在二分图最大匹配的名下，最常见的题面长这样：有若干个人，若干项任务，已知某些人能做某些任务，每个人最多被分配一项任务，每项任务也最多分配给一个人，问最多能安排多少人上岗。

剥掉故事外衣，它就是图论里的经典模型：把人看成左侧点集，把任务看成右侧点集，人和任务之间的“能做”关系看成边。“每个人最多做一项、每项最多一个人做”就是在限制匹配的合法条件。我们要找的，是所有这些不相交的边里数量最多的那一组。

很多同学第一眼看到这题会觉得像贪心：把人的关系排个序，能匹配就匹配。但贪心在这里是错的。举个最简单的反例：甲能干活1和2，乙只能干活1。如果贪心让甲先占掉1，乙就没活干，总匹配数是1；最优解明明是甲干2、乙干1，匹配数是2。匈牙利算法解决的就是这类需要“回头让位”的配对问题。

1.2 为什么这题必须用二分图

题目里人只和任务连边，人与人之间、任务与任务之间没有边，这种天然分成左右两侧的图就是二分图。之所以必须先识别出二分图，是因为普通图上的最大匹配问题要难得多，而后面的所有模板代码都建立在“两侧点集独立”这个性质上。

匈牙利算法的每一步操作都依赖左右两侧的点之分：从左侧点出发，沿边走到右侧点，再沿着匹配边回左侧点。如果图里有同侧边，这条路径就乱套了。所以当你拿到“人员分配”这类题，第一步不是背代码，而是确认模型可不可用：点和点之间能分成两组，所有边的两端分别落在两组里，符合就大胆上匈牙利算法。

顺带说一句，二分图匹配也常被包装成“选课”“社团招新”“棋盘覆盖”等题目。题面再花哨，只要你能把对象分成互不干扰的两拨，边只出现在两拨之间，核心就是同一个模型。

2. 匈牙利算法：从“占座”理解增广路

2.1 “让一让”的整个过程

匈牙利算法的执行过程，用占座来类比最直观。假设自习室里有几把椅子，每个同学能坐其中几把，一把椅子只能坐一个人。新来的同学先试自己能坐的椅子，如果有空位直接坐下；如果椅子被占了，他就问占座的同学能不能挪到别处，那个同学再去看自己的备选椅子，不行就继续往下问。

这个“连锁询问”在算法里叫DFS找增广路。实现上，我们把当前同学能坐的所有椅子逐个试一遍：椅子没人坐，直接匹配；椅子有人坐，尝试让坐在上面的人重新找一把椅子，如果那个人能成功换座，当前的匹配数就加一。

整个过程里最关键的是那个“visited”数组。同一轮尝试里，已经被问过的椅子不能再问第二遍，否则会死循环：甲问乙能不能挪，乙回头又问甲能不能挪，两个人互相踢皮球。visited数组就是为了标记“这轮问过了，别再回头”。

2.2 为什么增广路能让匹配数加一

从图论角度，增广路是一条“未匹配边、匹配边、未匹配边、匹配边、未匹配边”交替出现，且首尾都是未匹配点的路径。沿着这条路径把所有匹配边变成未匹配边、未匹配边变成匹配边，匹配数一定会增加1，因为路径上的匹配边比未匹配边少一条。

回到占座例子：新同学坐了一把被占的椅子，占座同学换到另一把空椅，原椅子空出来后新同学坐下。椅子和人的对应关系看似发生了内部调整，整体匹配数确定地从原来的数量变成了数量加一。

这个性质是匈牙利算法的灵魂。DFS里每一趟成功返回true，都等价于找到了一条增广路，匹配数全局加一。我们对外层循环里每个左侧点都尝试找一次增广路，最终得到的就是最大匹配。

2.3 正确性边界：何时可以收手

为什么对所有左侧点跑一遍DFS就一定是最大匹配？这里依赖一个匹配论中的经典结论：一个匹配是最大匹配，当且仅当图中不存在增广路。简单来说，如果还能找到一条增广路，匹配数就能继续增加，说明当前不是最大；反过来，如果怎么都找不到增广路，就再没有让匹配数变大的办法了。

按左侧点编号逐个跑DFS，每个点跑完都尝试消除一条“潜在增广路”。最终所有点都试完仍无增广路，匹配达到最大。这个过程不需要反复重跑多轮，因为外层每个左侧点都只启动一次DFS，内部通过换座已经把所有可能的影响链条走完了。

这也是匈牙利算法和网络流求最大匹配的一个区别。网络流要多次BFS分层、反复推流，匈牙利算法则是一轮DFS贯穿全场。理解了这个正确性依据，你背板子时就不会怀疑“是不是还要外层再循环几遍”。

3. 模板级实现：邻接表、DFS、match数组

3.1 核心代码逐行讲

先给一份最常用的DFS实现模板，我默认左侧点编号从1开始，右侧点编号也从1开始，但左右编号相互独立。

#include <bits/stdc++.h> using namespace std; const int MAXN = 1005; vector<int> g[MAXN]; // 左部点到右部点的邻接表 int matchRight[MAXN]; // 右部点当前匹配的左部点编号，0表示未匹配 bool vis[MAXN]; // 本轮DFS中，右部点是否被访问过 bool dfs(int u) { for (int v : g[u]) { if (vis[v]) continue; // 这轮已经尝试过，跳过 vis[v] = true; if (matchRight[v] == 0 || dfs(matchRight[v])) { matchRight[v] = u; // 右点配给左点 return true; } } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, k; cin >> n >> m >> k; // n个左点，m个右点，k条关系 for (int i = 1; i <= k; i++) { int u, 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 << "\n"; return 0; }

这个模板的复杂度是O(n乘m的量级)，准确说是O(VE)，V是左点数和右点数之和，E是边数。竞赛里n和边数在几千量级时完全够用。

3.2 三个容易写错的位置

第一个高频错误是把matchRight误当成“左点匹配到右点”的数组。题目里左右编号可能都是1开头，一个match数组存不下两组方向，所以你必须明确：matchRight下标是右点编号，存的是左点编号。如果你写成matchLeft，DFS里的换座逻辑就会变得混乱，代码越改越乱。

第二个高频错误是忘掉在每轮外层循环开始前清空vis。vis数组记录的是“当前这轮DFS尝试中有没有访问过某个右点”，它只对一次增广路查找有效。如果不清空，外层第二个左点开始搜索时，所有右点都标记成访问过，DFS直接全部跳过，匹配数就只能停留在第一轮的结果。

第三个坑是初始值。如果编号从1开始，matchRight应该初始化为0表示空；如果你习惯用vector并初始化为-1，判断条件就要相应改成matchRight[v] == -1。最忌讳的是一会儿用0一会儿用-1，同一个程序里两种约定混着写，查错能查掉半天。

3.3 完整可提交模板的边界处理

我建议把模板固定成一套习惯：左点编号1到n，右点编号1到m，matchRight值为0表示未匹配，vis数组只标右点。这样写的好处是，任何题目你只要把建图部分替换掉，其他代码可以原封不动地复用。

多人测试数据时，模板还需要加入清空操作。如果一组数据跑完要跑下一组，邻接表要逐条清空，matchRight要整体归零。我习惯把所有清空操作封装成一个init函数，在main里读入每组数据后先调用一遍，防止上一组残留数据影响下一组。虽然模板题通常只有一组数据，但竞赛里“多组数据直到EOF”很常见，提前做好准备能省下大量调试时间。

四、模板题上机过程与代码落地

4.1 套用SSL1338的建图方式

假设题目输入是n个人、m项任务、k条关系，每行两个整数表示某人能做某事，输出最多匹配人数。那么建图就是在读入每条关系时，把右侧任务编号加入左侧人的邻接表。

有一种题目变体需要留意：关系条数里可能出现重复边。重复边对最大匹配没有任何影响，DFS扫到同一条邻接边两次也无所谓，顶多多几次无效尝试。所以别在判重上浪费时间，直接加进邻接表就好。

还有一种变体是输入没有显式给出右侧点数m，只在关系里出现任务编号。此时m可以动态取所有任务编号里的最大值，或者干脆开一个足够大的数组。遇到这种情况，建议读入时顺手把任务编号的最大值维护出来，一方面用于确认右点范围，另一方面避免开小了数组导致越界。

4.2 右侧点数量比左侧点多时怎么办

匈牙利算法外层循环遍历的是左侧点。如果右侧点数远大于左侧，依然遍历左侧点没有问题，匹配数不可能超过左侧点数。反过来，如果左侧点数远大于右侧，遍历左侧点可能会重复尝试很多注定失败的DFS，此时可以把左右两侧交换再跑一遍。

交换左右侧点集是一种常用优化：我们总是让外层遍历点数更少的一侧。因为ans不会超过小的那侧点数，外层循环越短，无效DFS越少，程序运行越快。在模板代码里，你只需要在建图时判断两侧点数量，把点少的一侧当作左侧，重新映射编号即可。

4.3 数据范围与递归深度的权衡

DFS实现天然依赖系统栈。当左侧点数量达到几万，且链式换座关系很长时，递归深度可能很深。虽然竞赛环境下C++的栈一般能扛住，但保险起见，如果左侧点数超过5万，建议改用栈模拟或Hopcroft-Karp算法。

另一个和递归深度相关的问题是段错误。如果程序在自测小数据时正常，大样例一跑就Segmentation Fault，排查顺序应该是：数组越界优先，递归爆栈其次。先把vector大小开够，再考虑改成非递归写法。

5. 实战排错：对拍、性能与经典翻车点

5.1 用暴力小数据验证模板

写匹配题最怕的不是算法错，是模板在极端情况下偷偷出错。我推荐的办法是写一个暴力验证器：直接枚举所有匹配组合，找出最大匹配数，然后随机生成小规模二分图，把暴力结果和匈牙利算法结果对拍。

暴力枚举组合数随点数量爆炸增长，只适合左侧点数不超过10的小数据。对拍脚本随机生成几百组测试，一旦两边结果不一致，马上能定位是模板某个边界条件写错。这套方法不只对模板题有用，任何图论算法上机前我都建议跑一轮暴力对拍。

5.2 复杂度陷阱：什么时候DFS版本会超时

O(VE)的匈牙利算法看着不大，但E可能很大。如果左侧1000个点、右侧1000个点、边数是稠密的50万条，最坏情况在DFS里反复换座，耗时就会明显上升。模板题通常不会卡这个量级，但实际项目或进阶题目就需要优化。

一种常见的省时技巧是邻接表排序。搜索时优先尝试“竞争者较少”的右侧点，能减少递归换座的次数。另一种更高级的做法是加剪枝：如果某个右边点已经匹配，而且它的匹配对象在当前这轮已经试过所有可能仍未成功，可以提前判断失败。不过这些优化对模板题本身意义不大，理解即可。

5.3 数据规模变大：Hopcroft-Karp与网络流

当点数量到10万级别，匈牙利算法的O(VE)就跑不动了。这时两个主流替代方案：

• Hopcroft-Karp算法：用BFS对增广路分层，再用DFS一次性寻找多条不相交的增广路径，复杂度降到O(E乘根号V)。
• Dinic最大流：把二分图建流网络，源点连左侧点，左侧点连右侧点，右侧点连汇点，容量都设为1，跑最大流得到最大匹配。单位容量的网络流跑二分图匹配同样非常高效。

模板题不需要用到这两个方案，但建议知道它们的存在。人员分配问题一旦换成“几十万人分任务”的企业级场景，或者套上带权约束（每个人对不同任务有不同收益，求总收益最大），匈牙利算法就演进成了KM算法或费用流问题。

6. 从最大匹配延伸出去的三个结论

6.1 最大匹配数与最小点覆盖数的一致性

二分图匹配里有一个经典结论：最大匹配数等于最小点覆盖数。点覆盖是指选出若干点，让每条边的至少一个端点被选中；最小点覆盖就是让这个点数尽量少。直观上，要让每条边都被覆盖，至少要拿走最大匹配中的每条匹配边的一个端点，所以覆盖数不可能小于匹配数；反过来又能构造出一组大小恰好等于最大匹配数的点覆盖。

这个结论在算法竞赛里经常被套壳考察。比如题目问“选择最少的检查站覆盖所有路线”，建模成二分图后，答案就是最大匹配数。很多同学只背了匹配模板，不知道怎么转成最小点覆盖，遇到这类题就卡住。我建议把这条对应关系记成口诀：最大匹配数等于最小点覆盖数。

6.2 最大独立集与最大匹配的换算

独立集是指选出若干点，让这些点之间没有任何边。对二分图来说，最大独立集的点数等于总点数减去最小点覆盖数，套用上面的结论，就变成总点数减去最大匹配数。实际题目里经常出现“在图中选尽量多互不干扰的点”，这种表述十有八九是在问最大独立集。

最典型的应用是棋盘问题：有些格子被占用不能选，有些必须选，没有任何两个选中的格子能互相攻击，问最多选多少。把棋盘染色成黑白两色，黑白格之间的攻击关系就是二分图的边，问题立刻变成最大独立集。这类题目表面看是搜索题，实际考点却是二分图匹配。

6.3 做题顺序与板子使用建议

我个人的建议是，先把这份DFS模板写成自己的固定版本，不要今天用数组明天用vector，后天又换成类封装。模板越统一，上机写题越不会出错。在掌握DFS版本后，再去学Hopcroft-Karp和网络流写法，形成一个由浅入深的技能梯度。

平时刷题时，每做一道匹配题，都顺手想一想：这道题能不能套最小点覆盖？能不能套最大独立集？能不能建网络流？这样一道模板题至少能扩展出三道衍生题的价值。等到真正比赛时，遇到“人员分配”这种直白题，你能在五分钟内写完整道题并通过，凭借的就是这种反复训练后的肌肉记忆。

我实际用过这个模板很多次，最想提醒你的一点是：vis数组的清空位置一定要放在外层循环里，而不是reset函数里。很多选手把memset写进了dfs函数开头，结果每深入一层递归就把所有访问标记清掉一次，造成了严重的逻辑错误。自己多写几遍，跑几组随机对拍，把这种低级错误彻底消灭掉，才算真正吃透这份模板。