[题目链接]

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 ; }

最新文章

  1. Android自定义View之圆环交替 等待效果
  2. [ASP.NET MVC 小牛之路]15 - Model Binding
  3. 使用ZooKeeper实现软负载均衡(原理)
  4. Orchard源码分析(1):Orchard架构
  5. 关于查询扩展版ESI高被引论文的说明
  6. 《Linux内核设计与实现》Chapter 3 读书笔记
  7. DropzoneJS 使用指南
  8. 红包算法思考和总结 -- by jason.zhi
  9. iOS开发:AVPlayer实现流音频边播边存
  10. 责任链模式(Chain of Responsibility Pattern)
  11. JAVA Web 之 struts2文件上传下载演示(二)(转)
  12. c中计时的几种方法
  13. Servlet 是否线程安全 看完便知
  14. iPhone 6 首发无大陆,DevStore要去香港吗?
  15. Windows技巧
  16. Windows下的wget,命令行下载url
  17. HTML浏览器标题栏如何设置
  18. 观光公交 [NOIP 2011] [思维推导]
  19. stark组件开发之批量操作
  20. ubantu 安装mysql 5.7 解决安装不提示设置密码问题

热门文章

  1. 接口测试(一)--soapui实践
  2. JS高级——词法作用域
  3. c#——值类型与引用类型
  4. java攻城师之路--复习java web之servlet
  5. c++选择文件夹对话框
  6. CAD保存DWG文件,设置保存的文件版本号和密码
  7. Linux之iptables(三、命令---&gt;单主机)
  8. sql server的 between and 日期问题
  9. UVALIVE 6958 Indoorienteering
  10. 详解Cookie、LocalStorage、SessionStorage