刷牛客网找华为OD机试真题的时候十个人里有八个会撞上这道矩阵匹配。我第一次见它的时候以为是二维数组排序的简单题结果看完题面才发现自己天真了。这道题出现在牛客网的华为OD真题库中核心考的是二分答案和二分图匹配一句话概括在行和列都不能重复的前提下从矩阵里挑n个数让这n个数中第k大的那个数尽量小。听起来绕但是理清思路之后它其实是OD算法题里性价比很高的一道经典题。这篇文章我就从题意拆解开始把二分匈牙利匹配的完整推导、Python和C可运行的代码、牛客网判题环境下的常见坑一次说清楚。1. 题目到底在说什么1.1 原题回忆与题意拆解这道题在牛客网上一般长这样第一行给三个整数 n、m、k然后给一个 n 行 m 列的矩阵 a。要求从每一行中恰好选一个数字同时要求这些被选中的数字不能在同一个列上重复出现换句话说最终选出来的 n 个数对应 n 个不同的行也对应 n 个不同的列也就是一个行到列的匹配。然后在所有满足条件的选法中把选出来的 n 个数从大到小排序第 k 大的那个数字记为 x问 x 最小可能是多少。这里需要先解释一下 n k 的含义。n 是行数也就是最终选出的数字个数m 是列数必须满足 m ≥ n否则 n 个数不可能分到 n 个不同列k 是题目要求关注的那个排名位置。k1 的时候我们关注的是选出的 n 个数里的最大值kn 的时候关注的是选出的 n 个数里的最小值。题目要我们求第 k 大的数的最小值本质上是一个“最大的最小”问题。注意区分这里不是简单地每行取最小值因为如果每行只取最小值这些最小值可能落在同一列这样就不满足“不同列”的约束了。我一开始刷这道题的时候就是先入为主以为把每行最小值拿出来排序取第 k 大就完事结果样例都过不了。所以理解“行不能重复 列不能重复”这个双重约束是解这道题的第一道门槛。有些版本的题面会说成“第k大的匹配值最小化”也有的会把矩阵描述成能力值或者排班关系但本质完全一样都是一张 n×m 的权值矩阵要选一个大小为 n 的匹配看匹配中第 k 大的边权。看到“矩阵”两个字就要敏感地意识到行和列大概率是被当作两类节点来处理的这为后面的二分图建模埋下伏笔。1.2 先看懂“第k大最小化”这句话“第 k 大最小化”这种描述在算法题里很常见也是最容易让新手晕的地方。我习惯把它翻译成判断型问题给定一个数 mid是否存在一种合法选法使得选出的 n 个数中第 k 大的数不超过 mid这个翻译很有用。因为如果存在一种选法让第 k 大的数 ≤ mid那么答案一定 ≤ mid如果不存在答案一定 mid。于是原来的“最优化问题”就变成了“可行性判断问题”为二分答案铺路。那怎么判断“选出的数中第 k 大的数 ≤ mid”呢我们可以换一个等价说法在选出的 n 个数中至少有 n-k1 个数是 ≤ mid 的。为什么是这个数把 n 个数从大到小排序若第 k 个位置上的数 ≤ mid那么从第 k 个位置开始一直到最后一共 n-k1 个位置这 n-k1 个数全部 ≤ mid。反过来说如果有至少 n-k1 个数 ≤ mid那么第 k 大的数也一定 ≤ mid。这个等价关系是整个二分答案的基石一定要在草稿纸上自己推一遍。这样check(mid) 的任务就变成了能否在行、列都不重复的前提下从矩阵中选出至少 n-k1 个值 ≤ mid 的数能mid 就可行不能mid 就不可行。有的同学会问那我们不是要选 n 个数吗只判断了其中 n-k1 个 ≤ mid剩下的那些数怎么办这是一个非常关键的问题我在后面讲为什么匹配数达到 n-k1 就够用的时候会详细说。这里先按下不表你先记住这个转化的结论原题等价于找最小的 mid使得矩阵中至少能挑出 n-k1 个 ≤ mid 的数且满足行列都不同。2. 解题思路为什么是二分答案 二分图匹配2.1 从“最大值最小化”想到二分答案看到“最小化第 k 大”或者“最小化最大值”这种描述第一反应就应该是二分答案。道理很简单前面已经说了我们要找的这个答案一定在矩阵中的某个元素值上而且它的取值范围不会超过矩阵元素的最小值到最大值。于是就可以用二分来逼近这个答案。具体来说把矩阵中的所有值拿出来去重排序或者直接在整个取值区间 [0, 1e9] 上二分。每一次取一个 mid去构造一个“只保留 ≤ mid 的位置”的子图然后在这个子图上判断有没有足够多符合条件的数字。如果 check(mid) 为真说明答案比 mid 小或等于 mid把上界收紧到 mid如果为假说明答案必须比 mid 大把下界收紧到 mid1。这种二分不是对索引二分而是对值域二分也就是经典的“答案二分”。之所以能这么干是因为判定条件具有单调性mid 越小可用的“好格子”越少越难选出 n-k1 个满足条件的数mid 越大可用的“好格子”越多可行性单调变好。单调性满足二分就安全。矩阵值可能很大比如 1e9但 log2(1e9) 大约 30 次也就是说只需要跑 30 次左右的匈牙利算法。而单次匈牙利是 O(V×E) 量级n 和 m 一般不超过 100所以总复杂度大概在 30 × 100 × 10000 3e7 级别在牛客网或者华为OD机试环境下都是完全能过的。2.2 用匈牙利算法检查可行性判断能否选出若干个数并且行和列都不能重复本质上是一个二分图最大匹配问题。把 n 行看成二分图左边的 n 个点把 m 列看成右边的 m 个点。如果矩阵第 i 行第 j 列的值 a[i][j] ≤ mid就在左边第 i 个点和右边第 j 个点之间连一条边。于是一个“匹配”就代表我们选择了矩阵里的一个数字左边的行唯一右边的列也唯一。我们要求的就是这个二分图里的最大匹配数。为什么要用匈牙利算法因为它是求二分图最大匹配最简单、最好写的算法核心思想就是“增广路径”从左边的点出发尝试去匹配右边的一个点如果右边这个点已经被别的左边点占用了就尝试让那个左边点再去找别的右边点把位置腾出来。这个“腾位置”的过程递归下去就能不断增大匹配数直到找不到增广路径为止。这里有一个容易写错的点每次从左边的第 i 个点出发做增广时需要一个 visited 数组作用是记录右边的哪些点已经在当前这一轮增广中被尝试过防止递归死循环。visited 数组必须每轮都重新初始化为 false这个细节漏掉的话程序会在某些数据上表现得很玄学。用矩阵匹配这道题来说左边点数 n 最大也就是百量级右边点数 m 也差不多匈牙利算法在这种数据规模下非常好使。如果 n 和 m 到了几千甚至上万那就得考虑 Hopcroft-Karp 算法了但是 OD 机试基本到不了这个规模不用提前给自己加戏。2.3 为什么匹配数 ≥ n-k1 就够了这是很多人看完题解依然卡住的地方包括我自己当初也没想通。我们明明要选 n 个数为什么 check(mid) 的时候只看最多能匹配多少个 ≤ mid 的数而不要求整个匹配达到 n 条边关键点在于剩下的那些数没有任何数值限制。题目只要求你“选 n 个数行列不重复”并没有要求这 n 个数都必须满足某种关系。所以只要我用 ≤ mid 的边找到了 n-k1 个互相不冲突的位置剩下的 k-1 行怎么办因为 m ≥ n而且这个矩阵是全满的每一行在每一个列上都有一个数字。也就是说当我们站在“剩余行”和“剩余列”的角度看剩下的格子天然构成一个完全二分图每个左点连到所有右点。在完全二分图上只要右边点的数量不少于左边点的数量就一定能找到一个完美匹配。前一步的匹配占用了 n-k1 个列剩余列数至少是 m-(n-k1)而剩余行数是 k-1因为 m ≥ n所以左侧点数 k-1 ≤ 右侧点数完全二分图必然可以完成匹配。因此 check(mid) 只需要判断最大匹配数是否大于等于 n-k1。这个结论很重要我建议你在草稿纸上画一个 3 行 4 列的例子k2 的情况试一下跑通了就彻底懂了。反过来说如果最大匹配数都不到 n-k1说明即使让剩下的那些行去选“任意大小”的格子也已经凑不齐“至少 n-k1 个 ≤ mid”的数量要求那 mid 就不可行。因为要想选出 n 个数且其中有至少 n-k1 个 ≤ mid那这 n-k1 个位置本身就必须构成一个匹配这是必要条件。3. 完整实现Python/C 代码与细节3.1 Python 实现含输入输出解析牛客网和华为OD机试采用的是 ACM 模式也就是自己写读入、自己写输出不像力扣那样只需要实现一个函数。所以代码里要处理 sys.stdin 的读取而不是默认给一个 Matrix 类。这是很多习惯了力扣的人第一次上牛客网最容易翻车的地方。下面是我在本地跑通、也在牛客网上提交过的 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)) a [] max_val 0 for _ in range(n): row [int(next(it)) for _ in range(m)] a.append(row) max_val max(max_val, max(row)) # 匈牙利算法求二分图最大匹配 def max_match(limit): # 邻接表左边的行 i 能连到右边的哪些列 j adj [[] for _ in range(n)] for i in range(n): for j in range(m): if a[i][j] limit: adj[i].append(j) match_to [-1] * m # 右边列 j 匹配到了哪个左点 def dfs(u, visited): for v in adj[u]: if visited[v]: continue visited[v] True if match_to[v] -1 or dfs(match_to[v], visited): match_to[v] u return True return False cnt 0 for u in range(n): visited [False] * m if dfs(u, visited): cnt 1 return cnt need n - k 1 lo, hi 0, max_val ans max_val while lo hi: mid (lo hi) // 2 if max_match(mid) need: ans mid hi mid - 1 else: lo mid 1 print(ans) if __name__ __main__: solve()这里的 max_match(limit) 函数把“值 ≤ limit”的边全部加入邻接表然后跑一次匈牙利算法。注意匈牙利算法的核心递归函数 dfs 里visited 是在每次从左点出发时重新创建的这个必须放在最外层循环里不能全局只用一个反复不清空的数组。3.2 C 实现要点如果机试你准备用 C核心逻辑一样但要注意两个点一是读入用 scanf 或 cin 都行数据量小性能不是问题二是匈牙利算法的递归写法在 n 和 m 都只有 100 左右时完全不用担心爆栈但如果数据范围放大到几千就建议改成非递归版。这里给出主要代码逻辑#include bits/stdc.h using namespace std; int n, m, k; int a[105][105]; vectorint adj[105]; int matchR[105]; bool dfs(int u, vectorbool vis) { for (int v : adj[u]) { if (vis[v]) continue; vis[v] true; if (matchR[v] -1 || dfs(matchR[v], vis)) { matchR[v] u; return true; } } return false; } int maxMatch(int limit) { for (int i 0; i n; i) adj[i].clear(); for (int i 0; i n; i) for (int j 0; j m; j) if (a[i][j] limit) adj[i].push_back(j); memset(matchR, -1, sizeof(matchR)); int cnt 0; for (int u 0; u n; u) { vectorbool vis(m, false); if (dfs(u, vis)) cnt; } return cnt; } int main() { scanf(%d%d%d, n, m, k); int maxVal 0; for (int i 0; i n; i) for (int j 0; j m; j) { scanf(%d, a[i][j]); maxVal max(maxVal, a[i][j]); } int need n - k 1; int lo 0, hi maxVal, ans maxVal; while (lo hi) { int mid (lo hi) / 2; if (maxMatch(mid) need) { ans mid; hi mid - 1; } else { lo mid 1; } } printf(%d\n, ans); return 0; }这个版本我本地测过2 到 3 组随机数据和暴力枚举的结果一致比较稳。C 在牛客网上的编译环境一般支持 C11上面这种 vector 和递归写法没问题。3.3 二分边界、图构建等实现细节二分边界写不好容易死循环或者答案错一位。我自己踩过的坑主要有这几个第一二分区间怎么定。最简单的是 lo0himaxVal矩阵元素最大值。因为矩阵元素可能全为非负数答案不可能小于 0也不可能大于矩阵元素最大值。如果你不确定矩阵元素是否会出现负数可以把 lo 初始化成 minVal但牛客网这题一般是非负整数从 0 开始最简单。第二循环条件用 lo hi并且记录 ansmid。当 check(mid) 可行时把 ans 更新为 mid然后 himid-1当不可行时lomid1。这样写最直观也不会漏答案。如果写成 lo hi 且不加 ans 记录就需要在循环结束时决定输出 lo 还是 hi容易把自己绕进去。第三max_match 里每次都要重建邻接表。很多同学为了省事把“边”全局建好再根据 limit 判断是否可用这种做法也可以但要注意匈牙利 dfs 里别真的递归到一条不可用的边。我上面这种每次重新建邻接表的方式更直观虽然看起来多花了 O(nm) 的构建时间但实际上 nm 很小完全无所谓。第四注意 match_to或 matchR数组的初始化。每次调用 max_match 都要把右边所有点的匹配对象重置为 -1。如果你忘了清上一次二分的结果残留下来那整个判定就乱了。这属于最基础的“状态清理”问题但越是紧张的时候越容易漏。4. 模拟案例手把手跑一遍4.1 样例输入与手动推演我们用一个简单的例子来手动验证一下思路。假设输入是3 4 2 1 5 9 2 3 4 7 8 6 2 8 1这里 n3m4k2要选 3 个数行列不重复让选出的 3 个数中第 2 大的数尽量小。先把矩阵写出来第1行: 1 5 9 2 第2行: 3 4 7 8 第3行: 6 2 8 1如果 mid2那么值 ≤2 的位置有 (0,0)1(0,3)2(2,1)2(2,3)1。我们看能否在这 4 个位置里选出至少 2 个行列都不同的位置。比如选 (0,0) 和 (2,1)可以或者选 (0,0) 和 (2,3)可以或者选 (0,3) 和 (2,1)也可以。最大匹配数至少是 2而 need 3-21 2。所以 mid2 可行。那答案会不会比 2 更小我们试试 mid1。值 ≤1 的位置只有 (0,0)1 和 (2,3)1这两个位置行不同、列也不同所以最大匹配数是 2仍然 ≥2说明 mid1 也可行。再试 mid0。矩阵中没有 ≤0 的位置最大匹配数为 0小于 need2不可行。因此答案就是 1。我们手动验证一下能否选出 3 个数使第 2 大的数等于 1可以(0,0)1(1,1)4(2,3)1选出的数是 1,4,1从大到小排序是 4,1,1第 2 大正好是 1。所以答案 1 成立。这个例子很好地说明了为什么不能每行取最小每行最小值是 1、3、1其中第3行最小值1在列3第1行最小值1在列0如果选 (0,0)1(1,?) 第2行最小值3在列0但列0被占所以只能退而求其次选第2行的其他列比如 (1,1)4。最终选法是 (0,0)1(1,1)4(2,3)1刚好和二分结果一样。4.2 结果验证把上面这个样例丢进代码程序会输出 1和我们的手动推演一致。我再给一个边界一点的样例方便你理解 kn 的情况2 3 2 4 9 1 2 8 7n2m3k2need 2-21 1。意思是只需要选出至少 1 个 ≤mid 的数即可。二分答案最终会收敛到矩阵的最小值 1因为只需要找到一个最小值所在位置剩下的行随便选一个不相冲突的列就行。第一行 (0,2)1第二行可以选 (1,0)2行列不同所以第 2 大的数是 2等等选出的数是 1 和 2从大到小是 2,1第 2 大是 1。对所以答案 1。那如果 k1 呢need n-11 n要求所有选出的 n 个数都 ≤mid也就是要找到一个完整的行-列匹配每条边都 ≤mid这就退化成了经典的“求最小化匹配中的最大边权”问题和带权二分图匹配中的瓶颈匹配完全一致。这些边界case对理解题目很有帮助建议刷题的时候都自己想一遍。5. 牛客网与华为OD机试的实战避坑5.1 ACM模式输入输出别栽跟头华为OD机试在牛客网上是 ACM 模式也就是说代码必须自己处理输入输出。很多从力扣转过来的同学第一次写牛客网题目直接定义了一个函数以为会有参数传进来结果提交报错才发现。矩阵匹配这道题第一行是 n、m、k之后是 n 行 m 列的矩阵中间可能有换行也可能有空格直接用 sys.stdin.read().split() 统一读进来是最省心的做法。C 就用 cin 或者 scanf 连续读不需要关心换行的位置。另外输出必须要换行。print(ans) 默认会换行C 的 printf(%d\n, ans) 也要把 \n 加上。有些判题系统对最后的换行不敏感但养成习惯总没错。还有一个很基础但容易被忽视的点读入结束之后先检查一下 n、m、k 是否都成功读到了。按照牛客网的格式这些数据一定都是存在的但本地调试时如果文件结尾多了一个空白行用 sys.stdin.read().strip().split() 解析时可能得到空列表提前做 if not data 的判空处理能避免不少麻烦。5.2 递归栈、数组越界、二分死循环匈牙利算法的递归深度最多是左边点数 nn 是 100 时根本不用担心爆栈但如果有些变种题把 n 放大到 1000递归深度达到 1000 在 Python 里默认递归限制是 1000就可能报 RecursionError。解决方法是开头加上 sys.setrecursionlimit(100000)虽然这道题用不到但写进模板里没坏处。数组越界是 C 写手最容易翻车的地方。矩阵匹配里右边是列下标范围是 0 到 m-1visited 和 matchR 数组的长度都应该按 m 开而不是按 n 开。我见过有人把 n 和 m 都定义成 105然后用的时候搞反在 nm 的时候碰巧过n≠m 的时候就崩了。这种问题在牛客网判题时会显示 Runtime Error排查方向就是数组下标。二分死循环也是一个高频问题。如果你用的是 lo hi 的写法mid 每次都在变不会死循环但如果你把条件写成 while (lo hi) 且 mid (lo hi) / 2在 check 为真时更新 lomid那当区间长度为 2 时就会无限循环。解决方法是记住一个口诀判断可行就收上界判断不可行就推下界边界自然二分如果你更习惯记录 ans 的写法就用 lo hi。5.3 OD机试备考节奏建议华为OD机试虽然本身不算编程竞赛但算法题覆盖率还挺高二分、动态规划、图论、字符串处理都有可能出现。矩阵匹配这道题的难度在OD真题里属于中档偏上因为它要求你同时掌握二分答案和二分图匹配两个知识点很多只会简单排序遍历的人到这里就会卡住。我的建议是如果目标是快速通过OD机试不要去盲目刷海量题目而是先把高频题型吃透。比如二分答案类的“最大值最小化/最小值最大化”问题、匈牙利算法解决的行列匹配问题、背包DP、最长递增子序列、拓扑排序等等。你可以按照题型分类刷每类刷透 3 到 5 道题比乱七八糟刷 50 道题效果要好得多。刷题平台就用牛客网的华为OD专区因为它贴近真实考试环境都是 ACM 模式。做题时还要刻意练习时间分配。OD机试一般有固定的时间限制矩阵匹配这种题如果一眼看不出思路最优策略是先跳过把简单的题目写出来拿分最后再回来啃。我自己的习惯是拿到一道题先花 3 分钟读题然后花 5 分钟想思路想不出来就换题绝不在一道题上死磕超过 15 分钟。这个习惯帮我避免过好几次整场崩盘。最后说一个白嫖技巧提交前先自己造几个简单样例尤其是 k1、kn、nm 这种边界情况跑一遍确认输出合理。这比什么“检查模板”都实在。矩阵匹配这道题我在牛客网提交时也遇到过本地跑正确、线上报错的情况最后发现是 Python 的递归函数里 visited 数组没有在当前分支正确回滚导致某条路径占用了不该占用的右点。改回来之后就一切正常了。如果你刷题时在这道题上卡了很久说明你对二分答案的“check函数设计”和匈牙利算法的模板还不够熟练。建议先把这两块分别练熟再回来做这道题一定会豁然开朗。这种“题目背景是华为OD但算法内核是二分二分图匹配”的题在真实机试里也有很高的复现率值得多刷几次。