bzoj2150: 部落战争(匈牙利)
2024-08-31 12:05:02
2150: 部落战争
题目:传送门
题解:
辣鸡数据..毁我AC率
先说做法,很容易就可以看出是二分图匹配的最小路径覆盖(可能是之前不久刚做过类似的题)
一开始还傻逼逼的去直接连边然后准备跑floyd...肯定是做祭祀做傻了
二分图嘛,将每个点拆成两个集合再连啊...
然后最小路径覆盖=总点数-最大匹配数
强烈吐槽!个人习惯用数组存点编号...50*50的数据范围我开55*55...结果WA n次
然后...改成56*56...AC。。。ORZ
代码:
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
struct node
{
int x,y,next;
}a[];int len,last[];
void ins(int x,int y)
{
len++;a[len].x=x;a[len].y=y;
a[len].next=last[x];last[x]=len;
}
char s[][];
int n,m,R,C,t;
int match[],chw[];
bool findmuniu(int x)
{
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(chw[y]!=t)
{
chw[y]=t;
if(match[y]== || findmuniu(match[y]))
{
match[y]=x;
return true;
}
}
}
return false;
}
int d[][];//辣鸡数据
int main()
{
scanf("%d%d%d%d",&n,&m,&R,&C);
for(int i=;i<=n;i++)scanf("%s",s[i]+);
int ss=;memset(d,-,sizeof(d));
for(int i=;i<=n;i++)for(int j=;j<=m;j++)d[i][j]=++ss;
const int dx[]={,R,R,C,C};
const int dy[]={,-C,C,-R,R};
int sum=;len=;memset(last,,sizeof(last));
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(s[i][j]=='.')
{
sum++;
for(int k=;k<=;k++)
{
int x=i+dx[k],y=j+dy[k];
if(d[x][y]!=- && s[x][y]!='x')
ins(d[i][j],d[x][y]+n*m);
}
}
memset(match,,sizeof(match));
memset(chw,,sizeof(chw));
int ans=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(s[i][j]=='.')
{
t++;
if(findmuniu(d[i][j]))ans++;
}
printf("%d\n",sum-ans);
return ;
}
最新文章
- 12Mybatis_用mapper代理的方式去开发以及总结mapper开发的一些问题
- 更改电脑与eclpse热键冲突
- Ehcache(2.9.x) - API Developer Guide, Cache Extensions
- Ajax 的同步与异步
- Knuth-Morris-Pratt Algorithm
- ListView 条目加载上滑下滑首尾缩放动画实现
- 前端学习笔记(zepto或jquery)——对li标签的相关操作(二)
- java-信息安全(二)-对称加密算法DES,3DES,AES,Blowfish,RC2,RC4
- phpstorm显示行号
- CSS3 动画及过渡详解
- HDP Hive StorageHandler 下推优化的坑
- laravel 不理解的call方法
- 排序算法系列:快速排序算法JAVA版(靠谱、清晰、真实、可用、不罗嗦版)
- 轻重搭配|计蒜客2019蓝桥杯省赛 B 组模拟赛(一)
- 20145317 网络对抗技术 逆向与Bof基础
- chromedriver下载安装
- nyoj Registration system
- hdu 5007
- 20155207王雪纯 Exp2 后门原理与实践
- IEEE Bigger系列题解
热门文章
- hdoj--3594--Cactus(tarjan)
- 【转】iOS多语言本地化(国际化)设置
- [jzoj 5662] 尺树寸泓 解题报告 (线段树+中序遍历)
- No changes detected or App &#39;blog&#39; could not be found. Is it in INSTALLED_APPS?
- 为IT程序员量身定制的12个目标——很经典
- sql server 清理数据库日志
- C++代码审查---参考林锐高质量C/C++
- IDEA里面的facets和artifacts的讲解
- Java 实现简单的RPC框架
- ntp.log日志梳理