题意：R行c列的草地中有些泥坑，FJ想用一些木板将泥坑盖住，但是又不想盖住了草地，已知木板可以任意长。问怎样用最少的木板将所有泥坑盖住？
分析：题意是很好理解，可是要想到二分匹配来做就难了，要想到那种构图的方法更是难上加难呀，太佩服了，这种构图方法反正我是怎么想也想不到的。
因为不能盖住草地，所以在某一行有可能出现多个横着的木板，所以不能只用一个点来表示一行，而是有多个点。同样列不能只用一个点来表示一列。将连续的点当成一个点建图，一条边仍然表示的是一个有泥地的方格
看题目中给的示例：
*.*.
.***
***.
..*.
转换成下面来个这样的矩阵：
1 0 2 0
0 3 3 3
4 4 4 0
0 0 5 0
---------
1 0 4 0
0 3 4 5
2 3 4 0
0 0 4 0
上面的矩阵是将每排连续的* 标记为一个点，下面的矩阵是将每列连续的*标记为一个点；这样，问题就可以转变为：俩个矩阵对应的非零位置，可以用横排覆盖也可以用纵列覆盖，例如（2,3）这个点，它可以被第一个矩阵中的3覆盖，也可以被第二个矩阵中的4覆盖，所以每一个非零的位置都是一个匹配，转变为求最小覆盖点集，也就是求出最大匹配，跟题目pku3041类似了
pku 2226
#include<iostream>
using namespace std;
int my[2555],mx[2555],r[255][255],c[255][255],nx,ny;
bool vis[2555],mat[2555][2555];
char g[51][51];
int path(int s)
{
for(int y=1;y<=ny;y++)
if(mat[s][y]&&!vis[y])
{
vis[y]=1;
if(my[y]==-1||path(my[y]))
{
my[y]=s;
return 1;
}
}
return 0;
}
int Max_Match()
{
memset(my,-1,sizeof(my));
memset(mx,-1,sizeof(mx));
int ans=0;
for(int i=1;i<=nx;i++)
{
if(mx[i]==-1)
{
memset(vis,0,sizeof(vis));
ans+=path(i);
}
}
return ans;
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
getchar();
for(int j=1;j<=m;j++)
scanf("%c",&g[i][j]);
}
nx=0;
memset(r,0,sizeof(r));
memset(c,0,sizeof(c));
memset(mat,0,sizeof(mat));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(g[i][j]=='*')
{
nx++;
for(int k=j;g[i][k]=='*';k++)
{
r[i][k]=nx;
j=k;
}
}
ny=0;
for(int j=1;j<=m;j++)
for(int i=1;i<=n;i++)
if(g[i][j]=='*')
{
ny++;
for(int k=i;g[k][j]=='*';k++)
{
c[k][j]=ny;
i=k;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(r[i][j]>0&&c[i][j]>0)
mat[r[i][j]][c[i][j]]=1;
}
printf("%d\n",Max_Match());
return 0;
}