第一次在牛客网上刷到“矩阵匹配”这道华为OD机试真题时我盯着题面看了很久第一反应是这不就是一个从矩阵里选数的题吗然后我试着按暴力组合去算复杂度发现排列数涨得离谱才意识到这道题真正的考点藏在两个词里二分答案、二分图匹配。如果你也在准备OD机试这道题值得单独拆一遍因为它正好把机试最爱考的两类能力串在一起——能不能从“求最值”想到“二分判定”以及能不能把矩阵里的行列约束翻译成一张图。下面直接按我实际调试到AC的过程来讲不绕弯子。1. 题目还原从三分钟读不懂到把行列约束翻译成匹配1.1 一个容易读歪的题面以我刷到的版本为例题面大概是这样的给定一个N行M列的矩阵满足N M现在要从每一行中选出一个数要求选出的N个数所在列互不相同问选出的这N个数中的最大值最小是多少。输入格式是第一行两个整数N和M接下来N行每行M个整数最后输出一个整数。比如2 2 1 2 3 4输出3这个样例很简单选(0,1)2和(1,0)3最大值为3如果选(0,0)1和(1,1)4最大值就是4。题目要求尽量让最大值变小所以答案是3。这里容易出问题的地方有两个。第一题目明确是“每行选一个”不是“每列选一个”所以最终选出的数量是N匹配的目标也是N条边。第二N和M不一定相等N M意味着右部节点列比左部节点行多这保证了一定存在至少一个完全匹配解。如果读题时把行列关系搞反二分图左右部建反了就会出现“样例能过、提交全错”的尴尬情况。1.2 从矩阵元素到二分图边很多第一次接触这道题的人都会问矩阵和二分图有什么关系其实关系非常直接。把每一行当成一个左部节点把每一列当成一个右部节点矩阵里的元素matrix[i][j]就可以理解为从第i行连到第j列的一条边边的权值就是这个元素值。于是题目要求“每行选一个数且列不能重复”翻译成图论语言就是从这张二分图里选出N条边任意两条边不能共享同一个左部节点或右部节点这就是一个大小为N的匹配。再叠加“让选出的这N个数最大值最小”这个条件就成了组合优化里的经典问题瓶颈匹配问题。所谓瓶颈就是指我们关心的不是匹配总权值而是匹配边权值里的最大值。这个转化是整个解题思路的地基后面所有代码都是在这张图上展开的。2. 从“选数”到“二分判定”暴力组合爆炸换来的单调性2.1 暴力解法的复杂度曲线如果不假思索直接暴力会出现什么情况每行选一列列不能重复本质上就是排列数路径数量大约是A(M, N)即从M个列里挑N个列再做一个排列。当N10、M10时就接近360万种可能等到N50、M50这个数字已经是天文数字。题目给出的范围通常在100这个量级暴力枚举必然超时。我也见过有人尝试用贪心每次取当前矩阵里的最小值然后删掉它所在的行和列再继续取。这个思路在部分小数据上看起来没问题但很容易被卡。因为一个局部最小的选择可能会把某个列占用导致后面需要更大元素来填坑全局最优往往需要“绕路”而贪心无法回退所以不能作为通用解法。2.2 单调性是二分答案的命门既然直接找最优解很难那就换个思路不要去问“最大值最小是多少”而是去问一个更简单的问题——给定一个上限limit能不能选出N个数使得每个数都不超过limit这个问题其实是一个判定问题它只回答“能”或“不能”。关键在于这个判定问题具有非常重要的单调性如果limit可行那么任何比limit更大的limit也一定可行因为矩阵里允许选的元素只会变多不会变少反过来如果limit不可行那么任何比limit更小的数也一定不可行。单调性一旦成立就可以用二分答案把“求最优值”变成“反复做判定”。这是整道题最核心的思维跳跃。二分答案的搜索范围也不需要从0到1e9瞎猜直接取矩阵元素的最小值和最大值即可因为最终答案一定等于矩阵中某个元素的值。搜索区间越小二分次数越少代码跑得越快。2.3 二分模板为什么这样写这里我直接给出这道题最顺手的二分写法int left minVal, right maxVal; while (left right) { int mid left (right - left) / 2; if (canMatch(mid)) { right mid; } else { left mid 1; } } System.out.println(left);两个边界动作需要理解透彻。当canMatch(mid)返回true说明mid是可行解但可能存在更小的可行值所以把右边界收缩到mid保留mid作为候选。当canMatch(mid)返回false说明mid不可行根据单调性所有小于mid的limit也不可能可行所以直接把左边界跳到mid 1彻底排除这些值。循环结束条件是left right也就是左右边界收敛到同一个点这个点就是最小的可行上限。这里特别注意给mid取中位数时建议写成left (right - left) / 2而不是(left right) / 2。虽然这道题数据范围不容易溢出但养成这个习惯可以避免在其他大范围题目里踩坑。3. 匈牙利算法在矩阵上的落地matchRight、visited 与 DFS3.1 “让座”逻辑匈牙利算法的一次直观解释二分答案搭好框架之后核心就剩下一个check函数给一个limit判断矩阵里能否凑出大小为N的匹配并且每条匹配边的权值都不超过limit。也就是在二分图中只有当matrix[row][col] limit时行节点row和列节点col之间才存在一条可用边。判断二分图最大匹配是否等于N最经典的做法是匈牙利算法。它的核心思想可以用一个特别生活化的场景记忆让座。每个左部节点依次去占一个右部节点如果这个右部节点已经被之前的某个左部节点占着那就让被占的左部节点试着换到别的右部节点去如果被占的节点能换成功当前节点就占位成功如果换不了就继续找下一个右部节点。实现上需要一个matchRight数组记录每个列当前被哪一个行占据默认值-1表示还没被占。还需要一个visited数组记录“当前这一轮尝试中哪些列已经被访问过”防止DFS在递归里绕圈子。每次给一个新行找位置时visited都要重新初始化。这一点极其关键我后面会专门讲它导致的翻车现场。3.2 完整可提交的 Java 实现下面是这道题在牛客网上的完整AC代码类名直接用Mainimport java.util.*; public class Main { private static int n, m; private static int[][] matrix; private static int[] matchRight; public static void main(String[] args) { Scanner sc new Scanner(System.in); while (sc.hasNext()) { n sc.nextInt(); m sc.nextInt(); matrix new int[n][m]; int minVal Integer.MAX_VALUE; int maxVal Integer.MIN_VALUE; for (int i 0; i n; i) { for (int j 0; j m; j) { matrix[i][j] sc.nextInt(); minVal Math.min(minVal, matrix[i][j]); maxVal Math.max(maxVal, matrix[i][j]); } } int left minVal, right maxVal; while (left right) { int mid left (right - left) / 2; if (canMatch(mid)) { right mid; } else { left mid 1; } } System.out.println(left); } } private static boolean canMatch(int limit) { matchRight new int[m]; Arrays.fill(matchRight, -1); for (int row 0; row n; row) { boolean[] visited new boolean[m]; if (!dfs(row, limit, visited)) { return false; } } return true; } private static boolean dfs(int row, int limit, boolean[] visited) { for (int col 0; col m; col) { if (matrix[row][col] limit !visited[col]) { visited[col] true; if (matchRight[col] -1 || dfs(matchRight[col], limit, visited)) { matchRight[col] row; return true; } } } return false; } }代码不长但每一部分都有明确职责。canMatch里重建matchRight并逐个行调用dfsdfs内部遍历列遇到一个可行且没访问过的列就标记visited并尝试占位如果列已经被其他行占位就递归尝试让那一行换位置。递归返回true就说明当前row最终能找到一个不冲突的列。这里有一个小优化如果在某一行dfs返回false说明当前limit下已经无法容纳这么多行直接返回false不用继续处理后面的行。这个提前剪枝在数据量大时能省不少时间。3.3 复杂度估算与语言选择匈牙利算法在邻接矩阵上的复杂度最坏情况下每个左部点跑一次DFS每次DFS递归过程中可能重新访问多个左部点每个左部点会遍历所有列所以整体是O(N^2 * M)。当N和M都在100左右时单次check大约是100 * 100 * 100 1e6次操作。二分次数则由值域范围决定。如果矩阵元素在10000以内只需要约14次二分即使值域扩大到1e9也只需要约31次二分总操作量在3000万级别Java在OJ上轻松跑进1秒。所以这道题用匈牙利算法完全够用不需要上最大流或KM算法。语言选择上牛客网支持Java、C、Python等主流语言。Java版本要注意类名必须是Main且不要带包名C版本只需要把matchRight数组换成vector dfs函数保持一致Python版本注意递归深度虽然N在100时不会爆栈但如果把dfs改写成递归要确认sys.setrecursionlimit已经调大。4. 牛客网提交的翻车现场多组输入、数组位置、二分方向4.1 visited 数组放错位置答案会“随机”这是我实际调试中最痛的一个教训。匈牙利算法里visited数组标记的是“当前这次增广尝试中已经访问过的列”它的生命周期只有一次DFS调用。正确做法是每尝试一个新行就新建一个boolean[m]数组传给dfs。如果把visited定义成全局变量并且不在每轮开始前清空那么行A尝试过的列在行B尝试时仍然被标记为true行B就会跳过一些本来可以使用的列导致匹配数偏小check函数返回错误结果。更坑的是这种错误不会导致编译失败也不会在自测小样例上一定暴露因为某些小数据碰巧没问题。它可能表现为本地跑几次结果时对时错或者在牛客网上随机性WA排查起来非常折磨人。所以写匈牙利算法时看到visited就条件反射地想这一轮清空了吗每一行开始前都重新初始化了吗如果没有直接就是雷。4.2 多组输入与 ACM 模式牛客网的华为OD机试题通常是ACM模式需要选手自己处理输入输出这和力扣那种给你一个函数签名、你只写核心逻辑的模式完全不同。我见过不少只在力扣刷题的同学第一次切到牛客网就懵了Scanner怎么读、类名为什么必须是Main、为什么结果要自己print。这些细节点在练习时需要提前适应。这道题在牛客网上有些版本是一组输入有些是多组输入直到EOF。稳妥做法是用while (sc.hasNext())包住整个处理流程这样单组和多组都能跑。如果题目明确只有一组这个写法也只会进入一次循环不会出错。输出用System.out.println每组数据输出一行中间不要额外打印空行。如果遇到特别大的输入量Scanner可能偏慢可以改用BufferedReader和StringTokenizer。但本题数据量不大Scanner够用优先保证逻辑清晰。4.3 二分方向写反和 mid 溢出二分答案方向的判断也很容易错。一定要先想清楚check返回true表示“当前limit可行”所以要让右边界往左找更小的可行值返回false表示“当前limit不可行”必须把左边界往上提。如果把true分支写成left mid 1逻辑就和单调性拧着来最终输出的值可能是错的而且不太容易一眼看出问题。还有一个隐藏坑是二分循环可能死循环。用while (left right)这套模板时mid left (right - left) / 2也就是向下取整。当left和right相差1时mid等于left。如果此时check(mid)为trueright变成mid也就是left不变但循环内左右边界会收缩到同一个值正常结束如果check(mid)为falseleft变成mid 1也就是right也会正常结束。所以这套模板不会死循环。反过来如果你自己改成mid (left right 1) / 2这种向上取整又不配合相应的边界收缩逻辑就很容易出问题。答案模板是死的关键是把边界含义理清。5. 手算 2x2 样例一次完整二分过程的逐步推演5.1 一个 2x2 样例的逐步推演很多人看代码会觉得懂了但自己动手推一遍才能真正理解二分和匈牙利是怎么配合的。就拿这个最简单的例子2 2 1 2 3 4矩阵最小值minVal1最大值maxVal4所以left1right4。第一轮mid2调用canMatch(2)也就是判断在元素不超过2的前提下能不能凑出2条匹配边。行0有矩阵值1和2所以行0可以连列0和列1行1的矩阵值是3和4都大于2所以行1没有任何可用边。第二行直接dfs失败canMatch返回false。于是left3。第二轮mid3调用canMatch(3)。这次行0可以连列0和列1行1的值3 3所以行1至少可以连列0。尝试让行0先匹配如果行0占了列0轮到行1时行1看向列0发现列0被行0占了于是递归让行0换到列1。列1是空的行0换过去成功行1顺利占下列0。这样两行匹配完成canMatch返回true。于是right3。此时left和right都等于3二分结束输出3。整个过程里第一次dfs的“换位置”操作就是匈牙利算法的增广路它是算法正确性的关键。如果行0不会“让座”行1就永远找不到列只能返回false那这道题会误判为不可行。5.2 一个 3x4 样例与输出再给一个稍微复杂一点的样例方便你在本地验证代码3 4 1 3 5 7 2 4 6 8 9 10 11 12输出是9选择方式是第三行必须选9列0因为它所在行的最小元素是9其他列更大第二行不能选列0了可以选4列1第一行选一个剩余列里较小的值比如5列2或3列1最大值为9。如果把上限压到8第三行所有元素都大于8没有任何可用边匹配数不可能达到3所以9就是最小可行上限。5.3 我实际提交遇到的三个问题第一个问题是visited重置位置。我有一次把visited定义成成员变量在canMatch开头初始化一次结果第一次跑通纯属运气第二次运行同样的输入匹配结果完全变了排查了半天才发现是这个原因。第二个问题是多组输入。我第一次提交时只处理了一组数据本地自测写的是单组输入样例全过但提交后OJ提示错误。后来把while (sc.hasNext())加上一次性彻底解决。第三个问题是二分范围和输出。一开始我图省事把二分范围写成0到10000虽然也能得到正确答案但当时为了测试还故意打印每次mid发现多跑了好几次无意义的循环。改成矩阵min到max之后逻辑更严谨效率也更高。后来我把打印语句去掉再提交就一路顺畅了。6. 从矩阵匹配引申出的通用套路最大值最小化 匹配/连通性判定6.1 识别这类题的三板斧“矩阵匹配”不是孤立的偏题它代表了一大类机试高频题型最大值最小化或最小值最大化。识别这类题可以靠三个特征。第一约束条件可以翻译成图或匹配。比如矩阵里的行和列互斥关系、网格里点与点的连接关系、任务与执行者之间的指派关系只要存在“每个节点只能用一次”的约束就优先往匹配、流、二分图上想。第二目标函数具有单调性。只要问题的答案是“可行区间的端点”而不是“中间的最优值”二分答案就有发挥空间。典型例子有让最大值尽量小、让最小值尽量大、判断限高后能否从起点走到终点。第三check函数通常是一个经典图算法。矩阵匹配的check函数是匈牙利算法网格路径类题目的check函数可能是BFS或DFS。二分只是外壳真正决定通过率的是你能否写出正确的check。6.2 数据范围变大后的升级方向如果题目把N、M放大到500甚至1000匈牙利算法的O(N^2 * M)就会吃紧。这时有两条路。一条路是把二分答案的次数降下来。如果矩阵值域可以离散化比如先收集所有矩阵元素值排序后去重再对这些离散值做二分那么二分次数从log(1e9)约31次降为log(元素个数)但离散化本身也有开销适合值域特别大但元素数量不多的场景。另一条路是升级匹配算法。把匈牙利算法换成Hopcroft-Karp复杂度降为O(E√V)在500量级下会明显更快。需要注意换成Hopcroft-Karp时建图方式也要从邻接矩阵改成邻接表否则复杂度优势发挥不出来。OD机试通常到不了这个数据规模但你如果拿这道题练手可以顺手把Hopcroft-Karp也写了当模板储备。6.3 相关变体和相似题目这道题还有一种变体把“每行选一个”改成“每列选一个”或者把“最大值最小”改成“最小值最大”。边界模板要相应调整。比如“最小值最大”时二分会改成如果check(mid)可行就尝试更大的值所以left mid否则right mid - 1。此时mid要取上中位数防止死循环。类似的题目在力扣和牛客上还有不少。比如“水位上升的泳池中游泳”就是典型的最大值最小化check函数用BFS或DFS判断连通性“最小化最大工作时间”的分配问题check函数用贪心或二分图匹配还有“隐藏的最大匹配”“任务调度”等等。核心思路完全一致先二分枚举答案再调用一个你已经会的图算法去判定。我个人在实际刷题中的体会是矩阵匹配这道题最值得反复练的地方不是背代码而是训练“如何从题目描述里识别出二分图和匹配模型”。你可以在草稿纸上把矩阵画出来把行列节点、可用边、匹配边都标清楚然后再写代码。把这道题彻底吃透之后再遇到类似的受限选择问题你会自然想到二分答案加匹配的组合而不是陷在暴力枚举里出不来。