poj 2226(最小覆盖)

题目链接:http://poj.org/problem?id=2226

思路:将连续的横向水洼看成X集合中的一个点,连续的纵向水洼看成Y集合中的一个点,而将每个水点看成一条边,它连接了所在的X集合中的点和Y集合中的点,于是问题就转化为求最小点覆盖了。最小覆盖=最大匹配。

http://paste.ubuntu.com/5942114/

原文地址:https://www.cnblogs.com/wally/p/3234167.html