二分图——最小覆盖poj2226
2024-09-06 07:42:12
详见进阶指南
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 1500
char mp[N][N];
int G[N][N],vis[N],match[N],n,m; bool dfs(int x){
for(int i=;i<=n;i++)
if(!vis[i] && G[x][i]){
vis[i]=;
if(!match[i] || dfs(match[i])){
match[i]=x;return ;
}
}
return ;
}
int work(){
int res=;
memset(match,,sizeof match);
for(int i=;i<=n;i++){
memset(vis,,sizeof vis);
if(dfs(i))res++;
}
return res;
} int cnt1,cnt2,id1[N][N],id2[N][N];//每个点对应的块序号
int main(){
for(int i=;i<=;i++)
for(int j=;j<=;j++)
mp[i][j]='.';
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("\n%c",&mp[i][j]);//这样很好用 //标记联通块
cnt1=,cnt2=;
memset(id1,,sizeof id1);
memset(id2,,sizeof id2);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(mp[i][j]=='*'){
if(mp[i][j-]==mp[i][j])
id1[i][j]=id1[i][j-];
else id1[i][j]=++cnt1;
if(mp[i-][j]==mp[i][j])
id2[i][j]=id2[i-][j];
else id2[i][j]=++cnt2;
} //建图
memset(G,,sizeof G);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(mp[i][j]=='*')
G[id1[i][j]][id2[i][j]]=;
n=max(cnt1,cnt2);
cout<<work()<<endl;
}
}
最新文章
- freemarker页面中文乱码
- CryptographicException异常处理方法
- Java程序员的日常 —— Java类加载中的顺序
- CentOS7安装mysql5
- java1.7集合源码阅读: Vector
- Heritrix源码分析(一) 包介绍(转)
- WCF学习系列二_使用IIS发布WCF服务
- IOS准备
- Masstransit开发基于消息传递的分布式应用
- Android 不通过USB数据线调试的方法
- 【BZOJ3450】【Tyvj1952】Easy 可能DP
- 初探LVS NAT与DR
- EF 6.x、EF Core实现dynamic动态查询和EF Core实现多个上下文实例池你了解多少?
- 最短Hamilton路径【状压DP】
- 下拉列表模仿placeholder效果
- ASP.NET Identity 三(转载)
- .NET Core2.0 使用EF做数据操作
- 用SLF4j/Logback打印日志-2
- 记自己的第一个完整的java web项目
- python学习笔记二:if语句及循环语句,断点,模块,pyc