在一个n*m的草地上，.代表草地，*代表水，现在要用宽度为1，长度不限的木板盖住水，
木板可以重叠，但是所有的草地都不能被木板覆盖。
问至少需要的木板数。
这类题的建图方法：
把矩阵作为一个二分图，以行列分别作为2个顶点集
首先以每一行来看，把这一行里面连续的*编号，作为一个顶点
再以每一列来看，把这一列里面连续的*编号，作为一个顶点
则每一个*都有2个编号，以行看时有一个，以列看时有一个，则把这2个编号连边，容量为1
再建一个源点，连接所有行的编号，一个汇点，连接所有列的编号
这道题要求的是，所有*都被覆盖，即找到一个顶点的集合S，使得任意边都有至少一个顶点属于
S,即求一个点集顶点覆盖S，又要木板数最少，所以求的就是最小顶点覆盖。
最小顶点覆盖怎么求？
二分图中，有：
最小顶点覆盖=最大匹配
所以这道题就转化为求二分图的最大匹配了
再转化为最大流dinic算法。
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue> using namespace std; const int maxn=;
const int inf=0x3f3f3f3f;
const int s=;
int t;
int tota;
int totb; inline int min(int x,int y)
{
return x<y?x:y;
} struct Edge
{
int to,cap,rev;
};
vector<Edge>edge[maxn];
int iter[maxn];
int level[maxn];
char str[][];
int hash[][]; void addedge(int from,int to,int cap)
{
edge[from].push_back((Edge){to,cap,edge[to].size()});
edge[to].push_back((Edge){from,,edge[from].size()-});
} void build_graph(int n,int m)
{
for(int i=;i<n*m;i++)
edge[i].clear();
tota=;
for(int i=;i<=n;i++)
{
int j=;
while(j<=m)
{
if(str[i][j]=='*')
{
tota++;
hash[i][j]=tota;
while(j<=m&&str[i][j+]=='*')
{
j++;
hash[i][j]=tota;
}
}
j++;
}
}
totb=tota;
for(int j=;j<=m;j++)
{
int i=;
while(i<=n)
{
if(str[i][j]=='*')
{
totb++;
addedge(hash[i][j],totb,);
while(i<=n&&str[i+][j]=='*')
{
i++;
addedge(hash[i][j],totb,);
}
}
i++;
}
}
t=tota+totb+;
for(int i=;i<=tota;i++)
addedge(s,i,);
for(int i=tota+;i<=totb;i++)
addedge(i,t,);
} void bfs()
{
memset(level,-,sizeof level);
queue<int>que;
while(!que.empty())
que.pop();
que.push(s);
level[s]=;
while(!que.empty())
{
int u=que.front();
que.pop();
for(int i=;i<edge[u].size();i++)
{
Edge &e=edge[u][i];
if(e.cap>&&level[e.to]<)
{
level[e.to]=level[u]+;
que.push(e.to);
}
}
}
} int dfs(int u,int f)
{
if(u==t)
return f;
for(int &i=iter[u];i<edge[u].size();i++)
{
Edge &e=edge[u][i];
if(e.cap>&&level[e.to]>level[u])
{
int d=dfs(e.to,min(f,e.cap));
if(d>)
{
e.cap-=d;
edge[e.to][e.rev].cap+=d;
return d;
} }
}
return ;
} int solve()
{
int flow=;
while(true)
{
bfs();
if(level[t]<)
return flow;
memset(iter,,sizeof iter);
int f;
while(f=dfs(s,inf))
{
flow+=f;
}
}
} int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
for(int i=;i<=n;i++)
{
scanf("%s",str[i]+);
}
build_graph(n,m);
printf("%d\n",solve());
}
return ;
}