求优于暴力法的矩阵行/列交点元素和最大化算法

问题定义 #

给定M×N的整数矩阵，需选择一组行和列，使得它们交点处的元素总和最大化，要求算法效率优于暴力枚举所有行/列组合的方式。

示例说明 #

高效算法：基于最大流-最小割的解法 #

暴力法时间复杂度为$O(2^{{M+N})$，仅能处理极小规模矩阵。以下方法将问题转化为最大流问题，时间复杂度可降至$O((M+N)}3)$（使用Dinic算法），适配绝大多数场景。

核心思路 #

将原问题转化为最小割问题，利用最大流-最小割定理求解：

1. 先统计矩阵中所有正元素的总和$P$——这是理论上的最大可能收益，若选择某些行/列引入负元素，则需从$P$中扣除对应损失。
2. 构建流网络，通过计算最小割找到需要放弃的最小收益，最终最大总和 = $P - \text{最小割容量}$。

具体步骤 #

1. 预处理计算

• 统计所有正元素的总和$P$。
• 对每一行$i$，计算该行所有正元素的和$\text{row_pos}[i]$；对每一列$j$，计算该列所有正元素的和$\text{col_pos}[j]$。

2. 构建流网络

创建包含源点$s$、汇点$t$的流网络：

• 源点$s$向每个行节点$u_i$连边，容量为$\text{row_pos}[i]$。
• 每个列节点$v_j$向汇点$t$连边，容量为$\text{col_pos}[j]$。
• 对每个负元素$\text{mat}[i][j]$，从行节点$u_i$向列节点$v_j$连边，容量为$|\text{mat}[i][j]|$（负元素的绝对值）。

3. 计算最大流与最小割

使用Dinic等高效最大流算法，计算从$s$到$t$的最大流。根据最大流-最小割定理，最大流的值等于最小割的容量。

4. 确定结果

• 最大总和 = $P - \text{最大流的值}$。
• 选中的行：残留网络中，能从源点$s$到达的行节点对应的行。
• 选中的列：残留网络中，能到达汇点$t$的列节点对应的列。

算法有效性说明 #

流网络的最小割对应最优取舍逻辑：

• 割掉$s$到行$i$的边，代表不选该行，放弃该行所有正元素收益。
• 割掉列$j$到$t$的边，代表不选该列，放弃该列所有正元素收益。
• 保留行$i$与列$j$的边（对应负元素），代表同时选该行和列，需承担该负元素的损失，损失通过边容量体现。

通过最小割找到放弃的最小总收益，即可得到最大的交点元素总和。

复杂度对比 #

• 暴力法：$O(2^{M+N})$，仅适用于M、N≤10的极小矩阵。
• 最大流解法：$O((M+N)^3)$，可轻松处理M、N≤500的矩阵。

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