如何求方阵选不共行列n个元素的最大可能mex值？

核心思路：二分答案 + 最大流（二分图匹配） #

我们的目标是找到最大的整数 m（即选中单元格集合的mex值），使得存在一个完美匹配（每行每列选一个单元格），其中 1, 2, ..., m-1 都出现在选中的单元格中，而 m 不在选中集合中（或 m 本身不存在于矩阵中）。

步骤说明 #

1. 二分答案范围

• 最小可能的 m 是 1（若完美匹配中没有1），最大可能的 m 是 max(矩阵中最大正整数 + 1, n+1)（若完美匹配包含1到n的所有数）。

2. 判断函数（关键）

对于给定的候选 m，我们需要判断是否存在一个完美匹配，包含所有 1 到 m-1 的数：

• 情况1：m=1：直接返回 true（没有小于1的正整数需要包含）。
• 情况2：m>1：
  1. 先检查矩阵中是否存在 1 到 m-1 的所有数，若有缺失则直接返回 false。
  2. 构造流网络并计算最大流，验证是否能同时满足完美匹配和包含所有 1 到 m-1 的数：
     • 流网络节点：源点 S、汇点 T、数节点（对应1到m-1）、行拆分节点（RowIn_i/RowOut_i，确保每行仅选一次）、列节点。
     • 边设置：
       • S → 数节点 Num_t：容量1，强制每个数t被选中至少一次。
       • Num_t → RowIn_i：容量1，仅当行i存在值为t的单元格。
       • S → RowIn_i：容量1，允许行i选择任意值的单元格。
       • RowIn_i → RowOut_i：容量1，限制每行仅使用一次。
       • RowOut_i → Col_j：容量1，对应矩阵中单元格(i,j)。
       • Col_j → T：容量1，限制每列仅选一次。
     • 验证条件：若最大流等于n（完美匹配的流量），且所有数节点Num_t都有流量流出（即每个t被选中），则返回true。

算法复杂度 #

• 二分答案次数：O(log M)，其中M为矩阵中最大正整数或n+1。
• 单次最大流复杂度：O(n³)（边数约为O(n²)，最大流为n）。
• 总复杂度：O(n³ log M)，适用于n≤100的规模。

示例验证 #

对于题目中的示例矩阵：

• 当m=3时，m-1=2，矩阵中存在1和2。构造流网络后计算最大流为4，且Num_1、Num_2均有流量流出，说明存在包含1和2的完美匹配，mex≥3。
• 当m=4时，m-1=3，矩阵中无3，直接返回false，说明mex<4。因此最大的m为3，与示例结果一致。

内容的提问来源于stack exchange，提问作者OXEN