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

把行连通块作为左部点,列连通块作为右部点,行列连通块有相交的格子就连边;

则问题转化为求最小点覆盖,即最大匹配。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int const MAXN=;
int R,C,bh[][][][],col[][],pre[MAXN],ans,cnt,head[MAXN],ct,bj;
char c[][],dc[];
bool vis[MAXN];
struct N{
int to,next;
N(int t=,int n=):to(t),next(n) {}
}edge[MAXN*];
void add(int x,int y)
{edge[++ct]=N(y,head[x]);head[x]=ct;}
bool dfs(int x)
{
for(int i=head[x];i;i=edge[i].next)
{
int u=edge[i].to;
if(!vis[u])
{
vis[u]=;
if(!pre[u]||dfs(pre[u]))
{pre[u]=x;return ;}
}
}
return ;
}
int main()
{
scanf("%d%d",&R,&C);
for(int i=;i<=R;i++)
{
cin>>dc;
for(int j=;j<=C;j++)
c[i][j]=dc[j-];
}
for(int i=;i<=R;i++)
{
int j=;
while(j<=C)
{
if(c[i][j]=='.'){j++;continue;}
cnt++;
while(c[i][j]=='*')col[i][j]=cnt,j++;
}
}
bj=cnt;
for(int j=;j<=C;j++)
{
int i=;
while(i<=R)
{
if(c[i][j]=='.'){i++;continue;}
cnt++;
while(c[i][j]=='*')
{
if(col[i][j])add(col[i][j],cnt);
i++;
}
}
}
for(int i=;i<=bj;i++)
{
memset(vis,,sizeof vis);
if(dfs(i))ans++;
}
printf("%d",ans);
return ;
}

最新文章

  1. CSS布局 -- 圣杯布局 &amp; 双飞翼布局
  2. 关于移动App的五个提问
  3. Jquery将&lt;a&gt;链接变为post请求
  4. 使用ArrayList时代码内部发生了什么(jdk1.7)?
  5. 最近i学习微信卡券中的会员卡功能,弄清楚不容易 ,分享一下。
  6. Angular2的input和output(原先的properties和events)
  7. 二、Redis安装
  8. CentOS 7 - 最小化安装后,解决无法使用yum命令问题!!
  9. 第一次:lesson eighty seven。
  10. WIN10 企业版 LTSC 激活
  11. Edusoho之LNMP环境搭建
  12. cmd解压压缩包
  13. Springboot配置时间格式
  14. Linux 命令详解(十)Shell脚本的数组详解
  15. 【C++】解决vs2015经常卡顿的办法
  16. 使用awk处理文本
  17. java.lang.IllegalArgumentException: No Retrofit annotation found. (parameter #1) for method ApiService.getMethod
  18. javaSrript_数据类型(2017-03-15)
  19. 非常简单的vue里面引入jquery
  20. meta标签的使用方法(PC端)

热门文章

  1. Azure Mobile App - Custom Authentication
  2. 嵌入式Linux驱动案例之中的一个
  3. Linux 学习之虚拟机下的网络连接
  4. sql time 比较
  5. Hive merge(小文件合并)
  6. Django1.11.4中文文档
  7. 调用Camera返回为空的分析及处理方法
  8. oracle基础操作(1)
  9. ffmpeg下载rtmp flv
  10. 最新wap手机agent