poj 2446 Chessboard (匈牙利算法)

2016年5月26日 0 作者 CrazyKK

poj 2446 题目链接
题意:一个n*m的矩形方格里,有k个坏点,然后问能否用1*2的矩形块将矩形方格填满。坏点不能填,小的矩形块不能重叠,不能超出边界。不能有好点没有被填。

思路:乍一看没什么好的思路。。。然后发现小的矩形块只能有两种放置方法(横着放,竖着放) 可能我们对于第i个,可以横着放,也可以竖着放,但是可能某种方案使得后面的某一块没办法放置,因此我们需要反过来调整第i块的放法。  这个过程似乎和二分图匹配有点类似。。?  那到底有没有相似点呢。。。又如何划分集合呢。。。?

如果每个小方格看做点,能不能填满,其实就等价与这些点的最大匹配数×2+坏点数=m*n是否成立。。。那如何划分集合呢。。。? 我们可以根据点的坐标的奇偶性划分集合。。。因为小矩形块是2*1的,所以容易知道,每块矩形块放置的两个点一定属于不同的集合。。这样就满足了二分图匹配问题的模型。。。

然后匈牙利搞之。

 

这题一开始WA了。。WA在没有注意到一个小细节,使得连边的时候,有的是左点指向右点,而有的连成了右点指向左点。