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