BZOJ 4554 [Tjoi2016&Heoi2016]游戏 ——二分图
2024-08-30 06:06:26
出原题,直接二分图匹配即可。
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i) vector <int> v[3005]; int n,m,map[55][55],mx,ans;
int le[55][55],ri[55][55],vis[3005],linker[3005];
char s[55]; bool dfs(int o)
{
for (int i=0;i<v[o].size();++i)
if (!vis[v[o][i]]){
vis[v[o][i]]=1;
if (!linker[v[o][i]]||dfs(linker[v[o][i]]))
{
linker[v[o][i]]=o;
return true;
}
}
return false;
} int main()
{
scanf("%d%d",&n,&m);
F(i,1,n)
{
scanf("%s",s+1);
F(j,1,m)
switch(s[j])
{
case '*': map[i][j]=1;break;
case '#': map[i][j]=-1;break;
case 'x': map[i][j]=0;break;
}
}
F(i,0,n+1) map[i][0]=map[i][m+1]=-1;
F(i,0,m+1) map[n+1][i]=map[0][i]=-1;
int cnt=0,con=1;
F(i,0,n) F(j,0,m)
if (map[i][j]!=-1) con=1,le[i][j]=cnt;
else{if (con) ++cnt,con=0;}
mx=cnt;cnt=0,con=1;
F(j,0,m) F(i,0,n)
if (map[i][j]!=-1) con=1,ri[i][j]=cnt;
else {if (con) ++cnt,con=0;}
F(i,1,n) F(j,1,m)
if (map[i][j]==1)
v[le[i][j]].push_back(ri[i][j]);
F(i,1,mx)
{
memset(vis,0,sizeof vis);
if (dfs(i)) ans++;
}
printf("%d\n",ans);
}
最新文章
- 在IDEA上跑eclipse开发的J2EE项目
- Matlab 语谱图(时频图)绘制与分析
- Cocoa的MVC架构分析 cocoa的mvc实现
- Rabbitmq init terminating in do boot 问题
- erlang程序优化点的总结(持续更新)
- spring jdbc 源码
- highcharts柱状图和饼图的数据填充
- MySQL优化三(InnoDB优化)
- 对接第三方平台JAVA接口问题推送和解决
- 团队作业4——第一次项目冲刺(Alpha版本)
- React Native之样式
- Eclipse install new software无反应
- Git是什么、Git的功能、为什么versioncontrol用Git、Git的常用命令、Git的优缺点
- Python——Redis相关知识
- js生成二维码 qrcode
- 淘宝Tengine 2.1.2 稳定版(nginx/1.6.2) Centos 6.5安装教程
- 文件编码检测.ZC
- Debug 单步执行命令step into/step out/step over的区别
- .netcore部署centos
- hdu4549矩阵快速幂+费马小定理