n×n表格每行每列数字唯一的最小单元格修改次数求解

问题重述 #

给定n×n表格，单元格数字范围1~2n，修改部分单元格后要求每行、每列数字互不相同，求最少需要修改的单元格数量。

示例输入：

1 1
2 1

示例答案：1

核心思路 #

最少修改数 = 总单元格数 - 最多可保留的单元格数。我们可以通过最大流网络模型计算最多可保留的单元格数量，具体步骤如下：

1. 构建流网络 #

构建包含5类节点的流网络：

• 源点S、汇点T
• 行节点：代表表格的n行，记为R₁到Rₙ
• 数字节点：代表1到2n的所有数字，记为X₁到X_{2n}
• 列节点：代表表格的n列，记为C₁到Cₙ

添加以下带容量约束的边：

• 源点S → 每个行节点Rᵢ：容量为n（每行最多可保留n个不同数字的单元格）
• 每个行节点Rᵢ → 数字节点Xₓ：容量为1，当且仅当原表格第i行中存在数字x（表示该行可以保留一个值为x的单元格）
• 源点S → 每个数字节点Xₓ：容量为min(原表格中x出现的次数, n)（最终表格中每个数字最多出现n次，每行一个）
• 每个数字节点Xₓ → 列节点Cⱼ：容量为1，当且仅当原表格第j列中存在数字x（表示该列可以保留一个值为x的单元格）
• 每个列节点Cⱼ → 汇点T：容量为n（每列最多可保留n个不同数字的单元格）

2. 计算最大流 #

求解上述流网络的最大流，最大流的数值就是最多可以保留的单元格数量——每条从S到T的流量路径S→Rᵢ→Xₓ→Cⱼ→T，对应保留第i行第j列的原数字x，且满足行、列无重复，数字x的使用次数不超限。

3. 计算最少修改数 #

用总单元格数n²减去最大流的数值，得到的就是最少需要修改的单元格数量。

示例验证 #

拿题目中的2×2表格举例：

• 原表格中数字1出现3次，数字2出现1次
• 构建流网络后，最大流为3（可保留3个单元格）
• 总单元格数4，所以最少修改数=4-3=1，与示例答案一致

模型合理性说明 #

流网络的边约束完美匹配问题的所有限制：

• 行节点的容量限制保证每行保留的数字互不重复
• 列节点的容量限制保证每列保留的数字互不重复
• 数字节点的容量限制保证每个数字在最终表格中最多出现n次
• 行到数字、数字到列的边限制，保证每个行-数字、列-数字组合最多保留一个单元格，避免同一行/列出现重复数字

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