poj 3041 Asteroids (二分图的最小顶点覆盖,匈牙利算法)

2016年5月30日 0 作者 CrazyKK

poj 3041题目链接
题意:一个n*n的网格中,有k个大小为1*1的小行星,现在可以用激光枪每次消灭一行的小行星或者消灭一列的小行星。问最少需要使用多少次激光枪消灭所有的小行星。

思路:一个建图技巧是:对于网格图,我们可以把某个格子的横纵坐标看成点,而格子所代表的内容看成边来建图。

如果我们按照这样的方式建图,那么这道题的行或者列就成了点,而小行星就成了边。我们要做得是选最少的点,使得这些点覆盖所有的边。

根据Knoig定理,二分图的最小顶点覆盖数等于二分图的最大匹配数。

匈牙利一遍即可。1A