Hungary

POJ-3020 Antenna Placement

题目传送门:POJ 3020

题意就是用圈来圈,求用多少圈能把圈完。

属于最大独立集问题,开始不知道这个,想了半天Orz。

最大独立集的定义是图中两两互不相邻的顶点构成的集合。

有个结论是最大独立集+最小覆盖集=V,而最小覆盖集=最大匹配,所以我们可匈牙利算法来做这个题。

POJ-3041 Asteroids

题目传送门:POJ 3041

题意为给你一个N*N的矩阵以及所有矩阵中小行星的位置,现在要用炸弹消灭所有的小行星,每个炸弹每次只能炸一行或者一列,求最少用多少炸弹能够消灭所有的小行星。这道题属于最小点覆盖问题。

图论中覆盖的含义是用一些顶点(或边)的集合,使得图中的每一条边(多一个顶点)都至少接触几何中的一个顶点(边)。

最小点覆盖问题就是用最少的点覆盖所有的边。

这里就有一个有趣的定理了……König定理:最小覆盖点数 == 最大匹配数