题解思路

问题理解与分析

我们需要从 $N \times M$ 矩阵中选出 $N$ 个数，满足：

1. 每行恰好选一个数
2. 每列恰好选一个数（因为 $N \leq M$，这是可能的）
3. 在所有这些选法中，找到第 $K$ 大的数的最小值

换句话说：在所有满足条件的选法中，我们想要让第 $K$ 大的数尽可能小。

核心洞察

1. 二分答案框架

这是一个典型的最大值最小化问题，适合用二分答案解决：

• 我们二分最终的答案 $x$
• 判定问题：是否存在一种选法，使得选出的 $N$ 个数中第 $K$ 大的数 $\leq x$

2. 判定条件的转化

"第 $K$ 大的数 $\leq x$" 等价于："至少有 $N-K+1$ 个数 $\leq x$"

为什么？

• 第 $K$ 大的数就是从小到大排序后的第 $(N-K+1)$ 个数
• 如果这个数 $\leq x$，那么它和所有比它小的数（共 $N-K+1$ 个）都 $\leq x$

算法框架

步骤1：二分答案

在矩阵元素的值域 $[min\_val, max\_val]$ 内二分

步骤2：判定函数设计

对于候选值 $mid$，我们需要判断：是否存在一种行-列匹配，使得至少 $N-K+1$ 个匹配的对应元素值 $\leq mid$

关键转化：这等价于检查二分图的最大匹配。

构建二分图：

• 左部：$N$ 个行节点
• 右部：$M$ 个列节点
• 边：如果 $A[i][j] \leq mid$，则在行 $i$ 和列 $j$ 之间连边

在这个二分图中，如果最大匹配大小 $\geq N-K+1$，则 $mid$ 可行。

为什么？

• 最大匹配大小表示最多能选出多少个 $\leq mid$ 的数
• 如果最多能选出 $\geq N-K+1$ 个，说明存在一种选法使得第 $K$ 大的数 $\leq mid$

技术细节

1. 二分图匹配算法选择

• 匈牙利算法：实现简单，复杂度 $O(N^2M)$
• 对于 $N, M \leq 250$ 的数据范围，匈牙利算法足够

2. 值域处理

矩阵元素的值域可能很大，但：

• 我们只需要在矩阵中实际出现的数值范围内二分
• 可以先去重排序，在 $O(NM \log(NM))$ 内完成

3. 正确性证明

单调性：如果 $mid$ 可行，那么所有 $mid' > mid$ 也可行（因为可选范围更大）。

充分性：如果最大匹配 $\geq N-K+1$，那么我们可以：

1. 先选择这 $N-K+1$ 个 $\leq mid$ 的数
2. 再为剩下的 $K-1$ 行任意选择其他数（肯定存在，因为 $N \leq M$）
3. 这样第 $K$ 大的数就是这 $N-K+1$ 个数中最大的，即 $\leq mid$

复杂度分析

• 二分次数：$O(\log(\text{值域范围}))$，约 $20-30$ 次
• 每次判定：匈牙利算法 $O(N^2M)$
• 总复杂度：$O(\log V \cdot N^2M)$，对于 $N,M \leq 250$ 可接受

样例分析

对于样例：

N=3, M=4, K=2
矩阵：
1 5 6 6
8 3 4 3  
6 8 6 3

我们二分答案：

• 当 $mid = 3$ 时，构建二分图（只连接值 $\leq 3$ 的边）：

  • 第1行：无
  • 第2行：列2(3), 列4(3)
  • 第3行：列4(3)

  最大匹配大小 = 2 $\geq N-K+1 = 2$，所以可行。

最终找到最小可行的 $mid = 3$。

优化技巧

1. 提前终止：如果当前 $mid$ 的匹配大小已经 $\geq N-K+1$，可以提前返回
2. 邻接表优化：只存储有效的边，减少内存使用
3. 值域离散化：如果值域很大，可以只对矩阵中实际出现的值二分

总结

这道题的关键在于：

1. 问题转化：将"第K大最小值"转化为二分答案问题
2. 判定条件：理解"第K大 ≤ x" ⇔ "至少有N-K+1个数 ≤ x"
3. 图论建模：用二分图匹配来检查可行性
4. 算法选择：根据数据范围选择合适的匹配算法

通过二分答案结合二分图匹配，可以高效地解决这个组合优化问题。