华为OD机试的题库在牛客网已经积累得很全了其中“矩阵匹配”这道题属于典型的高频题。我第一次刷到它的时候第一反应是“这不就是个搜索吗DFS全排列走一遍”真正上手才发现完全不是那么回事直接用搜索在数据规模稍微大一点的时候就会直接爆炸。后来认真把它拆解了一遍才发现这道题的精髓其实藏在两个地方一个是怎么把“行和列互斥”这层约束翻译成图论模型另一个是怎么把一个“第k大最小化”的最值问题转成二分答案判定性问题。这篇文章我就以牛客网收录的“矩阵匹配”真题为背景完整聊一聊题目的考点、建模思路、匈牙利算法的实现细节以及在机试实战中容易踩的坑。如果你是正在准备华为OD机试或者平时在牛客网刷算法题时对“二分图匹配”这类题目有点怵那这篇内容应该能帮你省不少力。1. 题目还原与考点拆解1.1 我看到的题面大概长什么样先说一下题面。牛客网和其他题库里流传的“矩阵匹配”版本很多常见的一种描述是给定一个 n 行 m 列的矩阵要求从矩阵中选出 n 个数字任意两个数字不能在同一行也不能在同一列求选出的这 n 个数字中第 k 大的数字的最小值。有的版本会写成“每行选一个数字所选数字所在列不能重复”意思是一样的。还有的版本会直接定义成“求最大数的最小值”那其实就是这个题目当 k1 时的特殊情况。第 k 大本质上是把最终选出的 n 个数从大到小排个序取第 k 个位置上的值我们要让这个值尽量小。输入输出方面牛客网这套题通常是标准 OJ 格式第一行给 n、m、k后面 n 行每行 m 个数。n 的范围一般不会特别大常见的是几十到一两百这个量级但已经足够让暴力搜排列的方法完全不可行了。具体数值范围以实际题目为准不影响解题思路。我这次按照最常见的“n 行 m 列选 n 个数不同行不同列求第 k 大最小值”这个版本来讲因为这个版本包含的信息最全。你如果看到的是“最大值最小”的简化版把 k 直接理解成 1 就行解法框架完全一致。1.2 这题到底在考什么这道题在华为OD机试里出现频率高不是因为它会直接考一个裸的“二分图最大匹配”而是因为它把两个算法思维揉在了一起。第一层是建图能力。题目里的约束“任意两个数字不能在同一行同一列”翻译过来就是每一行只能对应一个列每一列也只能被选择一次。这天然就是一个二分图匹配模型左侧是 n 行右侧是 m 列矩阵里的每个位置就是一条从行节点连到列节点的边。我们要做的事情等价于在这个二分图里找到一个覆盖所有行节点的匹配也就是一个大小为 n 的匹配。第二层是二分答案能力。题目不是直接问你“能不能选出 n 个满足条件的数”而是问“选出的数里第 k 大的值最小是多少”。这种问法非常典型如果正面去构造最优解需要同时考虑选的哪几个数、顺序怎么排、k 的位置在哪复杂度会很难看。但反过来如果给定一个阈值 x让你判断“能不能选出一组数使得第 k 大的数不超过 x”就会简单很多。这种“求最值”转“判可行性”的思路就是二分答案。所以这道题表面上是矩阵题实际上考察的是二分图匹配模板和二分答案套路的组合。这两个点都是机试高频考点放在一道题里难度一下就上来了。1.3 机试为什么爱出这种题我在牛客网刷华为OD真题的时候一个很明显的感受是机试题目很少考那种“背个模板就能过”的裸题它更喜欢把基础算法包装在一个具体的场景里。“矩阵匹配”这题就是典型。如果你只会背匈牙利算法的代码但看不出来这道题其实在建二分图那基本就卡在第一步。反过来如果你只会二分答案但不知道匹配数怎么算也会卡在判定函数的实现上。这种出题方式还有一个好处就是能筛掉那些“背题型”的选手。因为它会让两个常规模型产生交叉匹配模型负责处理行列冲突二分答案负责处理最值问题。你必须真正理解两个模型的本质才能在考场上把它们的接口接起来。这种能力恰恰是实际工作中做业务系统设计时经常用到的把一个复杂需求拆解成若干个已知可解的模块。2. 建模思路为什么想到二分图和二分答案2.1 暴力思路和它的天花板很多第一次见这道题的人第一反应是枚举所有选择方案。因为要选 n 个数每个数在不同行不同列本质上就是给 n 行各分配一个不同的列。n 行对应 n 个列号的一个排列方案数就是排列数 n!。如果 n 只有 8 或者 10全排列然后逐个计算第 k 大的值完全没问题。可一旦 n 到 15 以上15! 大概是 1.3 万亿直接跑不动。机试的数据哪怕比较温和n 到 50、100 都很常见暴力思路基本就是拿部分分都费劲。还有同学会想到状态压缩 DP。对列做状态压缩用 dp[mask] 表示处理了前多少行、已经占用了哪些列转移时枚举当前行选哪一列。这个思路对 n 20 的数据是可行的复杂度大概是 O(n * 2^m) 再乘一个转移枚举二进制枚举 2^20 已经是百万级勉强能接受。但如果 m 到 50以上状态数直接爆掉。所以我们需要一个多项式复杂度的解法而二分图匹配是最自然的选择。2.2 把行和列看成二分图这里我多说几句建模的过程因为这个“翻译”太关键了。把矩阵的 n 行看成二分图左侧的 n 个节点把 m 列看成右侧的 m 个节点。矩阵里第 i 行第 j 列的位置就看成从左边的行节点 i 连到右边列节点 j 的一条边。题目要求选出的 n 个数字“不能在同一行也不能在同一列”翻译到这张二分图里就是我们要从左边每个节点出发给每个行节点匹配一个不同的列节点且所有匹配边对应的数字都是矩阵中真实存在的位置。这不就是一个大小为 n 的二分图匹配问题吗如果只是随便匹配 n 条边那当然有很多种方案所以还需要结合题目给的“第 k 大的数最小”这个目标。这种抽象能力是这类题的核心。生活和工作中也有大量类似的例子比如排班问题、任务分配问题、抢单问题本质都是“一组资源对应一组需求每个资源只能用一次”通通可以建模成二分图匹配。你把这个模型记熟了以后遇到任何“互斥分配”的题第一反应就不再是暴力搜索。2.3 第 k 大的最小化怎么处理直接求第 k 大最小值一眼看过去并不好做因为第 k 大这个位置本身就在变化。但是一旦我们转成二分答案思路就顺了。假设我们猜一个答案 x问题是能不能找到 n 个不同行不同列的数使得选出的这 n 个数中第 k 大的数不超过 x“第 k 大的数不超过 x”意思就是在选出的 n 个数里至少有 n-k1 个数小于等于 x。因为把这 n 个数按从大到小排序后第 k 个位置上的数不超过 x说明排在它后面的 n-k 个数也都不会比它大所以整个序列里至少有 n-k1 个数不超过 x。于是判定条件就变成了在只保留“数值 x”的边的子图里能不能找到至少 n-k1 条互不冲突的匹配边。为什么这里只数“符合条件的边”就够了因为题目并没有要求 n 条边全部符合条件。我们只要能先选出足够多的小于等于 x 的边剩下的行和列在完全二分图里总能补上毕竟矩阵里每一行每一列之间都有边。只要能补满 n 条其中符合条件的有 n-k1 条那第 k 大的值就不会超过 x。明白了这个逻辑二分答案就成立了。答案越小符合条件的边越少匹配数就越少越不满足答案越大符合条件的边越多匹配数越多越容易满足。存在一个明显的单调性正好可以用二分搜索来逼近最小可行值。3. 判定函数和匈牙利算法实操3.1 匈牙利算法的直觉与流程现在核心问题变成了给定一个阈值 x如何快速判断“值不超过 x 的边”里最大能匹配多少条这里用的就是经典的匈牙利算法。很多同学怕它其实直觉很好理解。把行节点当成求职者把列节点当成岗位每个求职者只对一部分岗位感兴趣。我们要做的是尽量多安排人上岗。如果当前求职者想去某个岗位但这个岗位已经被人占了那我们就试着让占了这个岗位的人换个岗位腾出位置给当前求职者。如果最终能让所有人都成功“上岗”就说明全都可以匹配。在代码实现里这个“让占位的人换岗位”的动作就是增广路径。我们用 DFS 去递归寻找可腾挪的岗位如果找到一条从当前行出发到某个空闲列的增广路径匹配数就能加一。这也是为什么匈牙利算法需要维护一个 matchR 数组用来记录当前右侧每个节点被哪个左侧节点匹配。模板本身不复杂但动态调整的时候很容易出错尤其是visited数组的清理时机。每尝试匹配一个行节点都要重新申请一个新的布尔数组保证在这一轮递归里每个列节点不会被无意义地重复访问。3.2 判定函数的构建细节对于“矩阵匹配”这题判定函数可以这样写遍历每行节点 u遍历每一列 v如果 matrix[u][v] 阈值 x说明这条边在当前子图里存在尝试为行 u 寻找列 v如果列 v 尚未匹配或者原本匹配这一列的行节点能换到其他列则匹配成功统计最终最大匹配数如果匹配数 n-k1返回 true否则返回 false。这里有一个细节经常被忽略阈值 x 决定的是哪些边“可见”。在 DFS 内部判断边的存在性时不能只看矩阵里有没有这个值还要看它是否小于等于当前阈值。这个条件是在每一步遍历列的时候动态判断的。还有一个容易想当然的地方我们要求的是“至少 n-k1 条匹配边”而不是必须匹配满 n 条。因为只要这些可行的低值边能匹配够数量剩下的边补上就行不一定非要全部 x。这一点与很多同学熟悉的“是否有完美匹配”的判定不同如果直接套模板写成匹配数等于 n 才返回 true在 k 1 的场景下就会漏掉正确答案。3.3 核心代码Python 版匈牙利匹配先给出一个 Python 版本的判定函数。这个版本在思路上最直白适合用来理解算法。def max_match_with_limit(limit): # 左侧 n 行右侧 m 列 match_col [-1] * m def dfs(u, seen): for v in range(m): # 只有 limit 的边才允许出现在当前判定的子图中 if matrix[u][v] limit and not seen[v]: seen[v] True if match_col[v] -1 or dfs(match_col[v], seen): match_col[v] u return True return False cnt 0 for u in range(n): seen [False] * m if dfs(u, seen): cnt 1 return cnt这段代码里的matrix是二维数组n是行数m是列数。每次判定传入一个limit相当于只保留数值不超过limit的边。函数返回当前子图下的最大匹配数。注意seen数组的位置。它必须放在for u in range(n)外面初始化并且每次尝试一个新的行节点前都重新置为全False。放在递归函数外部并跨行复用是最常见的错误之一轻则慢重则直接匹配出错。3.4 二分搜索边界怎么写有了判定函数二分答案就很简单了。因为最终答案一定来自矩阵中的某个数值所以左边界取矩阵最小值右边界取矩阵最大值即可。lo min(min(row) for row in matrix) hi max(max(row) for row in matrix) while lo hi: mid (lo hi) // 2 if max_match_with_limit(mid) n - k 1: hi mid else: lo mid 1 print(lo)这里选择的是最常见的“求最小值”二分框架可行就收缩右边界不可行就收缩左边界。最终lo就是满足条件的最小阈值。有些同学喜欢把hi初始化为一个很大的数比如 10^9其实也没问题但会浪费几次判定。拿矩阵元素本身的最大值来初始化能少跑几轮并且答案一定在这个区间里。还有一种优化是先把矩阵所有值排序二分下标而不是二分数值本身这样可以进一步减少二分的循环次数。不过对于机试来说直接二分数值通常已经够用。4. 完整可运行代码与OJ注意事项4.1 Python 完整版把上面的模块拼到一起就是一个能直接提交的版本。import sys def solve(): data sys.stdin.read().strip().split() if not data: return it iter(data) n int(next(it)) m int(next(it)) k int(next(it)) matrix [] for _ in range(n): row [int(next(it)) for _ in range(m)] matrix.append(row) def max_match_with_limit(limit): match_col [-1] * m def dfs(u, seen): for v in range(m): if matrix[u][v] limit and not seen[v]: seen[v] True if match_col[v] -1 or dfs(match_col[v], seen): match_col[v] u return True return False cnt 0 for u in range(n): seen [False] * m if dfs(u, seen): cnt 1 return cnt lo min(min(row) for row in matrix) hi max(max(row) for row in matrix) while lo hi: mid (lo hi) // 2 if max_match_with_limit(mid) n - k 1: hi mid else: lo mid 1 print(lo) if __name__ __main__: solve()这个版本我尽量写得干净方便在牛客网这种 OJ 上直接跑。sys.stdin.read()一次性读取所有输入避免逐行读取时的换行符边界问题这也是很多 OJ 题解常用的写法。如果担心 Python 在数据量稍大时卡常数可以换 PyPy 提交牛客网通常支持。还有一个小优化是在判定函数里预先建好“当前阈值下可用的边表”但那样会增加代码量也会让新手理解难度上升。机试场景下先把能过的版本写出来再考虑优化才是更实际的做法。4.2 C 版核心实现如果你平时用 C 刷题可以参考下面这个版本整体逻辑和 Python 版完全一致。#include bits/stdc.h using namespace std; int n, m, k; vectorvectorint a; bool dfs(int u, vectorint seen, vectorint matchR, int limit) { for (int v 0; v m; v) { if (a[u][v] limit !seen[v]) { seen[v] 1; if (matchR[v] -1 || dfs(matchR[v], seen, matchR, limit)) { matchR[v] u; return true; } } } return false; } bool ok(int limit) { vectorint matchR(m, -1); int cnt 0; for (int u 0; u n; u) { vectorint seen(m, 0); if (dfs(u, seen, matchR, limit)) cnt; } return cnt n - k 1; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m k; a.assign(n, vectorint(m)); int lo INT_MAX, hi INT_MIN; for (int i 0; i n; i) { for (int j 0; j m; j) { cin a[i][j]; lo min(lo, a[i][j]); hi max(hi, a[i][j]); } } while (lo hi) { int mid (lo hi) / 2; if (ok(mid)) hi mid; else lo mid 1; } cout lo \n; return 0; }C 版在递归时要注意参数传递。seen和matchR必须在每轮匹配中保持一致所以通过引用传入 DFS。matchR是右侧列节点的匹配对象数组初始化为 -1表示还没有任何行占用这一列。从性能角度说这段代码在 n、m 都在 100 左右时可以很稳地跑过。就算矩阵规模到 300 左右C 也基本没问题。4.3 牛客网OJ的输入输出注意事项这里分享几个我在牛客网刷 OD 题时踩过的实际坑。首先牛客网的输入格式有时候有多组测试数据有时候是单组。如果题目描述里没强调多组默认按单组处理即可但建议你在读输入时用sys.stdin.read().split()这种统一方式它可以自动把空格和换行都切开不会因为换行边界出错。其次输出不要带多余的提示文字。之前有同学在代码里写了cout result: ans endl;本地测试没问题一提交就是 Wrong Answer。OJ 只认标准输出里的数值任何多余字符都会导致判题失败。还有一个容易被忽略的点矩阵的行列顺序。题目给的输入是n m k然后矩阵是 n 行 m 列。你的匹配数组大小、循环次数都必须和题目一致。如果把 n 和 m 搞反小数据可能碰巧能过一旦测试点变大就会各种越界或者答案错误。5. 常见问题与避坑指南5.1 匹配数组的大小和含义搞混匈牙利算法里match_col[v]表示右列 v 当前被哪一行匹配数组长度应该是 m。但有的同学写成match_row[u]然后 DFS 里又把它当成列数组用逻辑就全乱了。我的建议是先用文字写清楚自己定义的映射方向。左侧是行右侧是列match_col的索引是列号值是行号。所有操作都以这个定义为准就不会乱。如果在调试时发现匹配数总是偏少但没有越界可以先在纸上画一个 3x3 的小矩阵手动跑一遍 DFS看看是不是在“让位”的逻辑上写错了。多跑几组小数据比反复猜测试点要有用得多。5.2 visited 数组的初始化位置错了这是所有匈牙利算法实现里最常见的 bug。seen数组表示当前这轮 DFS 中哪些列已经被尝试过。它必须在每次尝试一个新的左侧节点前重置。我见过一个很隐蔽的写法把seen定义在函数外部然后在 DFS 开头直接memset(seen, 0, sizeof seen)表面上看每次递归都会重置但这样会把当前递归路径上已经访问过的列重新开放导致死循环或错误匹配。正确做法很简单每次从左节点 u 开始尝试匹配时新建一个长度为 m 的布尔数组并传入 DFS。这样既不会冲突也不会导致同一轮递归里重复访问同一列。5.3 二分边界和判定目标写错二分边界方面左边界不能初始化成 0除非矩阵里的确有可能出现 0。应该取矩阵元素的最小值右边界取最大值。否则会出现一个问题当左边界过低时即使判定函数返回 false二分也会继续往右走最终答案可能落在两个矩阵值之间然后因为循环条件lo hi停在错误位置上。判定目标方面这道题是“匹配数 n - k 1”不是“匹配数 n”。把这两个搞混是在 k 大于 1 时出错的主要原因。特别是题目如果写的是“最大值最小”那 k1匹配数必须等于 n但一旦 k2、3再要求所有边都满足阈值就太严格了。5.4 递归深度和性能隐患DFS 递归在匹配链很长时可能爆栈尤其是当 n 到了几百级别。Python 默认递归深度只有 1000 左右虽然匈牙利算法的递归深度理论上最大可能是 n但如果 n 接近 1000就要小心。最常见解决办法有两个一是把递归改写成显式栈不过实现复杂度较高二是通过增加sys.setrecursionlimit(1000000)来放宽限制。机试数据规模通常可控所以大多数情况直接加递归限制就行。如果判定超时优先检查是不是每次二分都对整个 n x m 矩阵做了遍历。很多同学会把“建图”和“判定”放在一起每次重新构造邻接表这非常耗时。更简单的性能优化是不要在 DFS 内去判断matrix[u][v] limit时反复读取二维数组而是每次判定前把满足条件的边先放进一个 vector 或者列表里再跑匹配。虽然代码会长一点但常数性能能提升不少。5.5 样例能过但提交就是 WA这个问题最折磨人。我的习惯是先用题目给的样例跑一遍然后自己造三组小数据。第一组是 k1 的边界用来验证匹配数等于 n 的情况。第二组是极端小值比如所有矩阵数字都相同这时答案应该就是这个相同的数值。第三组是 n1 的情况此时只有一行无论 m 多大都只能选一个数第 k 大就是这个数本身答案应该是这一行的最小值k1时。这三组数据能过滤掉绝大多数逻辑 bug。如果还是找不到问题就在判定函数内部打印匹配数手动跟踪某个阈值的匹配过程。比如打印出当前阈值下每行匹配到了哪一列这样能很直观地看到是不是“低值边匹配数够了但补边逻辑没想对”。6. 机试刷题的一点体会“矩阵匹配”这道题在我刷牛客网华为OD真题的过程中算不上最难但它非常典型。它让我意识到机试考察的不只是你会不会背模板而是你能不能把一个看起来像搜索、像DP、甚至像贪心的题一步步剥出真正的算法内核。我自己在刷题时有个习惯每道题看完题目后先不急着写代码先在草稿纸上写下三行话。第一行写清楚输入是什么第二行写清楚最终要输出的最值是什么第三行写清楚题目里的限制条件可以抽象成什么结构。对“矩阵匹配”来说这三行答案分别是“n*m矩阵里的数值”、“第k大的最小值”、“不同行不同列 - 二分图匹配”。三行写明白了代码结构其实就出来了。如果你正在准备机试建议把匈牙利算法和二分答案这两个模板练熟但更重要的是练习“把题目翻译成模型”的敏感度。你可以把牛客网上华为OD题库里的题按模型分类比如哪些是匹配、哪些是 DP、哪些是图论最短路。混着刷比按标签刷更有用因为考试的时候不会提前告诉你这题该用哪个算法。最后再分享一个小技巧如果考场上有题目和“矩阵匹配”类似但不确定是不是二分图匹配可以先想想“行和列是否互斥”“每行是否只能选一个”“选了某一行是否会影响另一行”。只要有这三个特征就往匹配模型上靠。匹配模型至少能帮你拿到一个可解释、可调试的解法比硬搜要靠谱得多。