求解清除N×M二进制矩阵所有1所需的最少箭支数量

问题重述 #

给定大小为N x M的二进制矩阵，箭支支持两种射击方式：

• 水平射击：选择行号x=k射击，可清除matrix[k][y]（0 <= y < M）位置的所有1
• 垂直射击：选择列号y=k射击，可清除matrix[x][k]（0 <= x < N）位置的所有1
  要求找到清除矩阵中全部1所需的最少箭支数量。

测试样例 #

输入：

0 0 1 1 0 0
0 1 0 0 1 0
0 0 0 1 0 0
0 0 1 1 0 0

输出：3
方案解释：

arrow-1 : x = 1
arrow-2 : y = 2
arrow-3 : y = 3

现有贪心思路的缺陷 #

你提到的「每次选剩余1数量最多的行/列射击，更新计数直到所有1被清除」的思路无法得到全局最优解，也不是高效的实现方式：

• 首先贪心策略本身不成立，举个最简单的反例：2×2全1矩阵，按贪心逻辑第一步选任意行/列（消除2个1），剩余2个1分属不同列/行，还需要2次射击，总共消耗3支箭，但实际最优解只需要选2行或者2列，2支箭就能清完所有1。
• 其次实现层面，因为行和列的清除范围存在重叠，每次射击后都要更新所有受影响的行、列剩余1计数，还要维护排序关系，实现繁琐且时间复杂度没有优势。

最优解法：二分图最小顶点覆盖 #

这个问题是经典的二分图应用场景，通过Konig定理可以保证得到全局最优解，实现逻辑清晰，复杂度可控。

建模方法 #

把问题转化为二分图问题：

• 二分图左部顶点：对应矩阵的每一行，每个顶点代表一次对该行的水平射击
• 二分图右部顶点：对应矩阵的每一列，每个顶点代表一次对该列的垂直射击
• 边规则：如果矩阵位置matrix[i][j] = 1，就在左部第i个行顶点和右部第j个列顶点之间连一条边。
  此时原问题等价于：选择最少的顶点（行/列），让图中所有边都至少有一个端点被选中——这就是二分图的最小顶点覆盖问题。

核心定理 #

根据二分图Konig定理：二分图的最小顶点覆盖数 = 二分图的最大匹配数。也就是说我们只需要求出上述二分图的最大匹配值，这个值就是需要的最少箭支数。

实现步骤 #

1. 遍历整个矩阵，对每个值为1的位置，记录对应行顶点到列顶点的连边
2. 选择算法求二分图最大匹配：
   • 中小规模矩阵可以直接用匈牙利算法，实现简单，时间复杂度O((N+M)*E)，E为矩阵中1的总数
   • 大规模矩阵（N、M在1e4量级以上）可以用Dinic网络流算法求最大匹配，时间复杂度O(E*sqrt(N+M))，效率更高
3. 求得的最大匹配值就是最终答案。

样例验证 #

对题目给出的样例建图后计算最大匹配，得到结果为3，和样例输出完全一致。

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