第一次在牛客网上刷到“矩阵匹配”这道华为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个列再做一个排列。当N=10、M=10时就接近360万种可能，等到N=50、M=50，这个数字已经是天文数字。题目给出的范围通常在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 与 DFS
3.1 “让座”逻辑：匈牙利算法的一次直观解释
二分答案搭好框架之后，核心就剩下一个check函数：给一个limit，判断矩阵里能否凑出大小为N的匹配，并且每条匹配边的权值都不超过limit。也就是在二分图中，只有当matrix[row][col] <= limit时，行节点row和列节点col之间才存在一条可用边。
判断二分图最大匹配是否等于N，最经典的做法是匈牙利算法。它的核心思想可以用一个特别生活化的场景记忆：让座。每个左部节点依次去占一个右部节点；如果这个右部节点已经被之前的某个左部节点占着，那就让被占的左部节点试着换到别的右部节点去；如果被占的节点能换成功，当前节点就占位成功；如果换不了，就继续找下一个右部节点。
实现上需要一个matchRight数组，记录每个列当前被哪一个行占据，默认值-1表示还没被占。还需要一个visited数组，记录“当前这一轮尝试中，哪些列已经被访问过”，防止DFS在递归里绕圈子。每次给一个新行找位置时，visited都要重新初始化。这一点极其关键，我后面会专门讲它导致的翻车现场。
3.2 完整可提交的 Java 实现
下面是这道题在牛客网上的完整AC代码，类名直接用Main：
import 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并逐个行调用dfs；dfs内部遍历列，遇到一个可行且没访问过的列，就标记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)为true，right变成mid，也就是left不变，但循环内左右边界会收缩到同一个值，正常结束；如果check(mid)为false，left变成mid + 1，也就是right，也会正常结束。所以这套模板不会死循环。反过来，如果你自己改成mid = (left + right + 1) / 2这种向上取整，又不配合相应的边界收缩逻辑，就很容易出问题。答案模板是死的，关键是把边界含义理清。
5. 手算 2x2 样例：一次完整二分过程的逐步推演
5.1 一个 2x2 样例的逐步推演
很多人看代码会觉得懂了，但自己动手推一遍才能真正理解二分和匈牙利是怎么配合的。就拿这个最简单的例子：
2 2 1 2 3 4矩阵最小值minVal=1，最大值maxVal=4，所以left=1，right=4。
第一轮：mid=2，调用canMatch(2)，也就是判断在元素不超过2的前提下，能不能凑出2条匹配边。行0有矩阵值1和2，所以行0可以连列0和列1；行1的矩阵值是3和4，都大于2，所以行1没有任何可用边。第二行直接dfs失败，canMatch返回false。于是left=3。
第二轮：mid=3，调用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。于是right=3。
此时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函数用贪心或二分图匹配；还有“隐藏的最大匹配”“任务调度”等等。核心思路完全一致：先二分枚举答案，再调用一个你已经会的图算法去判定。
我个人在实际刷题中的体会是，矩阵匹配这道题最值得反复练的地方不是背代码，而是训练“如何从题目描述里识别出二分图和匹配模型”。你可以在草稿纸上把矩阵画出来，把行列节点、可用边、匹配边都标清楚，然后再写代码。把这道题彻底吃透之后，再遇到类似的受限选择问题，你会自然想到二分答案加匹配的组合，而不是陷在暴力枚举里出不来。
