对asteroids标记为1,其余标记为0，那么问题就是对一个01矩阵,选择若干行和列,可以覆盖所有的1

可以这样建二分图:以行号为左节点,列号为右节点,i行j列为1，那么i和j有条边,那么问题
就是从左边和右边选择最少的点可以覆盖所有的边,这不就是最小覆盖问题吗?

由König定理,一个二分图中的最小点覆盖数等于这个图中的最大匹配数，那么问题就划归
为求2分图的最大匹配

PS:最后,再说一下如何找出这些点(即行和列)，用匈牙利求出最大匹配后,从左边的未
匹配点出发，找一条“一条没被匹配、一条已经匹配。。。”的路径,对路径上的点进行标记
，最后所有左边未标记的和右边已标记的点即为最小覆盖点

• 用匈牙利算法的话，好像可以直接得到点（即行和列）的位置。 (0) 623611963 2011-04-25 19:47:43