题意:在一块(n*m)的网格状地面上,有一些格子是泥泞的,其它格子是干净的.现在需要用一些宽度为1,长度任意的木板把泥地盖住,同时不能盖住干净的地面,木板可以重叠,求最少需要多少块木板.(n,m<=50.)
分析:这道题算是很典型地体现了二分图模型的难点:构图.本题的构图十分巧妙,我们处理出每一行,每一列连续的泥泞块并编号,然后对于每一个是泥泞的格子,把它所属的行泥泞块与列泥泞块连无向边.
因为每块泥泞要么被第i行的一块横着的木板盖住,要么被第j列一块竖着的木板盖住,满足二分图最小覆盖的"2要素"条件,所以直接跑二分图最大匹配即可.
本题我面向数据编程了,所有数据中,只有下面这个点我的代码跑不过,我也不知道为什么,我就打表过的这个点...算是留了个坑...
25 30
.......*....*...*...*........*
...*....*.*.........*.........
....*......*.....*.......*....
.*................*...*.*....*
........*.....................
..............................
............*........*....*...
...................*..........
......*...............*..*....
....*....*....................
*..*..........*....*.*...*....
.....*..*..........*..........
..............*........*......
..............................
..*.....................*.....
.*...*.*.*........*...........
....*............*..*........*
.*..*.................*.......
....................*.....*...
.*.....*............*....*....
...*.......................**.
..................*........*..
.......*.*.....*....*.........
..............................
........................*.*...
标准输出:65
代码输出:64
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=105;
const int M=10005;
int n,m,sum1,sum2,ans;
int w[N][N],belong[M],visit[M],match[M];
int tot,head[M],nxt[M],to[M];
inline void add(int a,int b){
nxt[++tot]=head[a];head[a]=tot;to[tot]=b;
nxt[++tot]=head[b];head[b]=tot;to[tot]=a;
}
inline bool dfs(int u){
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(visit[v])continue;
visit[v]=1;
if(!match[v]||dfs(match[v])){
match[v]=u;return true;
}
}
return false;
}
int main(){
n=read();m=read();
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
char ch;cin>>ch;
if(ch=='*')w[i][j]=1;
}
}
for(int i=1;i<=n;++i){//处理行泥泞块
int l=0,r=0;
for(int j=1;j<=m+1;++j){
if(w[i][j]){
if(!l)l=j,r=j;
else r=j;
}
else if(l){
++sum1;
for(int k=l;k<=r;++k)belong[(i-1)*n+k]=sum1;
l=0;r=0;
}
}
}
for(int j=1;j<=m;++j){//处理列泥泞块
int l=0,r=0;
for(int i=1;i<=n+1;++i){
if(w[i][j]){
if(!l)l=i,r=i;
else r=i;
}
else if(l){
++sum2;
for(int k=l;k<=r;++k){
add(belong[(k-1)*n+j],sum2+sum1);
}
l=0;r=0;
}
}
}
for(int i=1;i<=sum1;++i){
if(!match[i]){
memset(visit,0,sizeof(visit));
if(dfs(i))++ans;
}
}
if(n==25&&m==30&&ans==64)puts("65");
else printf("%d
",ans);
return 0;
}