[USACO2005][POJ2226]Muddy Fields(二分图最小点覆盖)

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

题意:给你一个字符矩阵,每个位置只能有"*"或者“.",连续的横着或者竖的“*"可以用一块木板覆盖,"."不能被覆盖,求最少用多少块木板才能把整张图里的"*"全覆盖住

分析:很巧妙的建图

将所有横着的连续的"*"看作二分图左边的点集,同理竖着的连续的"*"看作二分图右边的点集

如果有横着的连续的"*"与竖着的连续的"*"相交,那么把这两个代表的点连边(每条边其实表示的一个原图的"*")

那么就是对建的图求最小点覆盖就行了,那么跑遍二分图最大匹配就行了

原文地址:https://www.cnblogs.com/wmrv587/p/3693167.html