poj 3041题目链接 题意：一个nn的网格中，有k个大小为11的小行星，现在可以用激光枪每次消灭一行的小行星或者消灭一列的小行星。问最少需要使用多少次激光枪消灭所有的小行星。 思路：一个建图技巧是：对于网格图，我们可以把某个格子的横纵坐标看成点，而格子所代表的内容看成边来建图。 如果我们按照这样的方式建图，那么这道题的行或者列就成了点，而小行星就成了边。我们要做得是选最少的点，使得这些点覆盖所有的边。 根据Knoig定理，二分图的最小顶点覆盖数等于二分图的最大匹配数。 匈牙利一遍即可。1A /* *********************************************** Author :111qqz …

poj 1325 题目链接 题意：有两台机器A和B,分别有n和m种工作模式。 现在有k个job,三元组（i,x,y),job i可以用A机器的x模式完成或者用B机器的y模式完成。初始两个机器都在模式0.机器更换模式的时候需要重启，问最少的重启次数。 思路：这道题的难点在于建图。。。每个job恰好对应了两种模式。。那么如果把模式看成点。。边就对应了这个job。。这样就是一个二分图。。。至于方向。。。怎么指都可以。。。统一就行。。 完全没有图的影子的题依然可以用图论解决。。。而且算是加深了对图这种模型的理解把。 然后这道题就变成了二分图的最小顶点覆盖。 **二分图中，选取最少的点数，使这些点和所有的边都有关联（把所有的边的覆盖），叫做最 …