本文共 935 字，大约阅读时间需要 3 分钟。

这道题的实现起来其实并不复杂，但理解起来可能需要一些思考。最开始，我想到的贪心法并没有成功，结果WA了。后来，我看到正确的解法后，逐渐理解了其中的图论原理。

首先，我们将行和列抽象成图中的两个点集，例如用点来表示行和列，小行星的出现则用边连接这些点。这样，问题就转化为求这个图的最小点覆盖。最小点覆盖问题在图论中属于NP难问题，但在这个特定问题中，我们可以借助最大二分匹配的方法来解决。

最小点覆盖与最大二分匹配的关系

在这个问题中，点覆盖的定义是：选择尽可能少的点，使得图中的每一条边至少有一个端点在这个点集中。为了找到最小的点覆盖数，我们可以将问题转化为寻找最大二分匹配数。具体来说，最大二分匹配的大小等于最小点覆盖数。

匈牙利算法的应用

为了找到最大二分匹配，我们可以使用匈牙利算法。这个算法通过构建增广路径来逐步增加匹配数。对于每个点，我们尝试找到一个未被匹配的邻居，并通过深度优先搜索来确定是否存在这样的路径。

代码实现

在代码中，我们定义了一个二维数组graph来表示小行星的位置。graph[r][c]为真，表示第r行和第c列有小行星。然后，我们使用匈牙利算法来计算最大二分匹配数。

匈牙利算法的大致步骤如下：

代码解析

• graph[r][c] = true：表示第r行和第c列有小行星。
• matches[i]：记录点i的匹配情况。
• dfs_visited数组用于记录深度优先搜索的状态。
• Hungarian_Aux函数尝试为点i找到一个匹配点，并返回匹配结果。
• Hungarian_Algorithm函数调用Hungarian_Aux多次，统计最大匹配数。

结果输出

程序读取输入后，计算并输出最大二分匹配数，即最小点覆盖数。这表示最少需要消灭的小行星行数或列数。

通过这种方法，我们将复杂的行或列消灭问题转化为图论中的匹配问题，成功地解决了问题。虽然开始时的贪心法没有成功，但通过抽象和转换，最终找到了正确的解决方案。

转载地址：http://ufxfk.baihongyu.com/