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

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

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

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

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

匈牙利一遍即可。1A

 

poj 1325 Machine Schedule(二分图的最小顶点覆盖,匈牙利算法)

poj 1325 题目链接
题意:有两台机器A和B,分别有n和m种工作模式。 现在有k个job,三元组(i,x,y),job i可以用A机器的x模式完成或者用B机器的y模式完成。初始两个机器都在模式0.机器更换模式的时候需要重启,问最少的重启次数。

 

思路:这道题的难点在于建图。。。每个job恰好对应了两种模式。。那么如果把模式看成点。。边就对应了这个job。。这样就是一个二分图。。。至于方向。。。怎么指都可以。。。统一就行。。

完全没有图的影子的题依然可以用图论解决。。。而且算是加深了对图这种模型的理解把。

 

然后这道题就变成了二分图的最小顶点覆盖。

二分图中,选取最少的点数,使这些点和所有的边都有关联(把所有的边的覆盖),叫做最小点覆盖。

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

一个证明:二分图最小顶点覆盖的证明

 

剩下的就是裸的hungary..

然而WA了好几次。。。

一个小细节没处理好。。。

由于初始是模式0.。。

所以模式0肯定要特殊考虑。。。因为初始状态是没有重启的。。。

但是我错误得以为只有当存在(i,0,0)这样的边时才忽略不算。。。

但是其实只要有一个端点是0就好了啊。。。不管哪端是0,我就用这个0来完成工作。。。依然不增加重启次数。。。

这不是什么坑点。。。脑袋秀逗了。。。