大意：如下图告诉你一个矩阵，让你用1 * x (x 为任意值） 的木板去铺符号* 可以覆盖
问最少多少木板能够把所有的*覆盖掉
4 4 *.*. .*** ***. ..*.
Boards 1, 2, 3 and 4 are placed as follows:
1.2.
.333
444.
..2.
Board 2 overlaps boards 3 and 4.
分析：
题目要求是把所有的点都覆盖掉
回忆一下之前做过的
这种类型的大概就是二分图的最小点覆盖或者最小边覆盖
那么怎么建立二分图呢
因为X是个不确定值
所以我们尽量让X取值越大越好
也就是说每一个横向或纵向的*区域都可以看做是一个联通块
那么只要把横向的连通块放在左集合，把纵向的连通块放在右集合 把点看左边
那么只要所有的边被覆盖则就是覆盖掉所有的*了
这样想来因为左右集合放的就是所求的连通块，那么只要求出最小点覆盖集即ok啦
最小点覆盖集 = 二分图最大匹配
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 using namespace std; 6 7 const int maxn = 55; 8 int G[maxn * maxn / 2][maxn * maxn / 2]; 9 10 int vis[maxn * maxn / 2]; 11 int Link[maxn * maxn / 2]; 12 int n; 13 bool Find(int u) { 14 for(int i = 1; i <= n; i++) { 15 if(G[u][i] && !vis[i]) { 16 vis[i] = 1; 17 if(Link[i] == -1 || Find(Link[i])) { 18 Link[i] = u; 19 return true; 20 } 21 } 22 } 23 return false; 24 } 25 26 int solve() { 27 int cnt = 0; 28 memset(Link, -1, sizeof(Link)); 29 for(int i = 1; i <= n; i++) { 30 memset(vis, 0, sizeof(vis)); 31 if(Find(i)) cnt++; 32 } 33 return cnt; 34 } 35 36 char mat[maxn][maxn]; 37 int vis1[maxn][maxn], vis2[maxn][maxn]; 38 int main() { 39 int m; 40 for(int i = 0; i <= 50; i++) { 41 mat[0][i] = mat[i][0] = ‘.‘; 42 } 43 while(EOF != scanf("%d %d",&n, &m)) { 44 for(int i = 1; i <= n; i++) { 45 for(int j = 1; j <= m; j++) { 46 scanf("\n%c",&mat[i][j]); 47 } 48 } 49 int tot1 = 1; int tot2 = 1; 50 memset(vis1, 0, sizeof(vis1)); memset(vis2, 0, sizeof(vis2)); 51 for(int i = 1; i <= n; i++) { 52 for(int j = 1; j <= m; j++) { 53 if(mat[i][j] == ‘*‘) { 54 if(!vis1[i][j - 1]) { 55 vis1[i][j] = tot1++; 56 } else { 57 vis1[i][j] = vis1[i][j - 1]; 58 } 59 if(!vis2[i - 1][j]) { 60 vis2[i][j] = tot2++; 61 } else { 62 vis2[i][j] = vis2[i - 1][j]; 63 } 64 } 65 } 66 } 67 memset(G, 0, sizeof(G)); 68 for(int i = 1; i <= n; i++) { 69 for(int j = 1; j <= m; j++) { 70 if(mat[i][j] == ‘*‘) { 71 G[vis1[i][j]][vis2[i][j]] = 1; 72 } 73 } 74 } 75 n = max(tot1, tot2); 76 printf("%d\n",solve()); 77 } 78 return 0; 79 }
poj2226Muddy Fields【最小点覆盖(建图的思路比较好）】,布布扣,bubuko.com
poj2226Muddy Fields【最小点覆盖(建图的思路比较好）】
原文：http://www.cnblogs.com/zhanzhao/p/3920295.html
