[BZOJ 1735] Muddy Fields
2024-08-30 06:13:26
[题目链接]
https://www.lydsy.com/JudgeOnline/problem.php?id=1735
[算法]
二分图最小覆盖
[代码]
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1010 struct edge
{
int to,nxt;
} e[MAXN * MAXN]; int i,j,n,m,ans,cntx,cnty,tot;
char mp[MAXN][MAXN];
int x[MAXN][MAXN],y[MAXN][MAXN];
int match[MAXN],head[MAXN];
bool visited[MAXN]; inline void addedge(int u,int v)
{
tot++;
e[tot] = (edge){v,head[u]};
head[u] = tot;
}
inline bool hungary(int u)
{
int i,v;
for (i = head[u]; i; i = e[i].nxt)
{
v = e[i].to;
if (!visited[v])
{
visited[v] = true;
if (!match[v] || hungary(match[v]))
{
match[v] = u;
return true;
}
}
}
return false;
} int main()
{ scanf("%d%d",&n,&m);
for (i = ; i <= n; i++) scanf("%s",mp[i] + );
for (i = ; i <= n; i++)
{
for (j = ; j <= m; j++)
{
if (mp[i][j] == '*')
{
x[i][j] = ++cntx;
while (j < m && mp[i][j + ] == '*')
{
j++;
x[i][j] = cntx;
}
}
}
}
for (j = ; j <= m; j++)
{
for (i = ; i <= n; i++)
{
if (mp[i][j] == '*')
{
y[i][j] = ++cnty;
while (i < n && mp[i + ][j] == '*')
{
i++;
y[i][j] = cnty;
}
}
}
}
for (i = ; i <= n; i++)
{
for (j = ; j <= m; j++)
{
if (mp[i][j] == '*')
addedge(x[i][j],y[i][j]);
}
}
for (i = ; i <= cntx; i++)
{
memset(visited,false,sizeof(visited));
if (hungary(i)) ans++;
}
printf("%d\n",ans); return ; }
最新文章
- Android自定义View之圆环交替 等待效果
- [ASP.NET MVC 小牛之路]15 - Model Binding
- 使用ZooKeeper实现软负载均衡(原理)
- Orchard源码分析(1):Orchard架构
- 关于查询扩展版ESI高被引论文的说明
- 《Linux内核设计与实现》Chapter 3 读书笔记
- DropzoneJS 使用指南
- 红包算法思考和总结 -- by jason.zhi
- iOS开发:AVPlayer实现流音频边播边存
- 责任链模式(Chain of Responsibility Pattern)
- JAVA Web 之 struts2文件上传下载演示(二)(转)
- c中计时的几种方法
- Servlet 是否线程安全 看完便知
- iPhone 6 首发无大陆,DevStore要去香港吗?
- Windows技巧
- Windows下的wget,命令行下载url
- HTML浏览器标题栏如何设置
- 观光公交 [NOIP 2011] [思维推导]
- stark组件开发之批量操作
- ubantu 安装mysql 5.7 解决安装不提示设置密码问题