POJ 2446 Chessboard

题意

给出一个M＊N大小的棋盘(M,N都非常小)，棋盘上戳了几个洞，然后问你有没有可能用若干张1*2的骨牌，横着或者竖着填满整个棋盘，有洞的地方是不可以放置骨牌的。

思路

因为骨牌是1*2的，如果我们把整个棋盘看成一个图，每个没洞的地方都是一个节点，在棋盘上只要相邻（上下左右四联通）就可以看成两个节点有一条边相连，这样我们就可以发现，每一块骨牌正好就是图上的一条边。所以我们就把问题转化为了：给出一个图，要你用选出尽可能少的边，使得图上的每一个顶点都是选出的边中的某一条的端末，也就是“最小边覆盖”问题。

最小边覆盖=图中点的个数-最大匹配数=最大独立集

所以接下来的事情就很简单，按着上面的说法建图，然后运行一次最大匹配算法，之后作个差就搞定了。

还要注意一点，本题数据给出的形式可能和预想的不一样，挖洞的点是横坐标在前，纵坐标在后，如果WA，不妨检查一下是不是输入的时候做反了。

代码

本实现使用了匈牙利算法。