[POJ]3020 Antenna Placement

The Global Aerial Research Centre has been allotted the task of building the fifth generation of mobile phone nets in Sweden. The most striking reason why they got the job, is their discovery of a new, highly noise resistant, antenna. It is called 4DAir, and comes in four types. Each type can only transmit and receive signals in a direction aligned with a (slightly skewed) latitudinal and longitudinal grid, because of the interacting electromagnetic field of the earth. The four types correspond to antennas operating in the directions north, west, south, and east, respectively. Below is an example picture of places of interest, depicted by twelve small rings, and nine 4DAir antennas depicted by ellipses covering them. 
 
Obviously, it is desirable to use as few antennas as possible, but still provide coverage for each place of interest. We model the problem as follows: Let A be a rectangular matrix describing the surface of Sweden, where an entry of A either is a point of interest, which must be covered by at least one antenna, or empty space. Antennas can only be positioned at an entry in A. When an antenna is placed at row r and column c, this entry is considered covered, but also one of the neighbouring entries (c+1,r),(c,r+1),(c-1,r), or (c,r-1), is covered depending on the type chosen for this particular antenna. What is the least number of antennas for which there exists a placement in A such that all points of interest are covered? 

这道题事实上就是让我们用最少的边覆盖所有的顶点，对于面板上的节点，每个节点的上下左右都有一个邻居，这样的图事实上是二分图，因为我们可以表示成下面的样子：

而上图很明显可以变为二分图，我们只需要把每隔一列把每一列染上相同的颜色即可。根据这篇文章，二分图的最小边覆盖 = N - 最大匹配，我们只需要跑对二分图跑匈牙利算法即可。时间复杂度O(V * E)，代码如下: