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

最新文章

  1. 12Mybatis_用mapper代理的方式去开发以及总结mapper开发的一些问题
  2. 更改电脑与eclpse热键冲突
  3. Ehcache(2.9.x) - API Developer Guide, Cache Extensions
  4. Ajax 的同步与异步
  5. Knuth-Morris-Pratt Algorithm
  6. ListView 条目加载上滑下滑首尾缩放动画实现
  7. 前端学习笔记(zepto或jquery)——对li标签的相关操作(二)
  8. java-信息安全(二)-对称加密算法DES,3DES,AES,Blowfish,RC2,RC4
  9. phpstorm显示行号
  10. CSS3 动画及过渡详解
  11. HDP Hive StorageHandler 下推优化的坑
  12. laravel 不理解的call方法
  13. 排序算法系列:快速排序算法JAVA版(靠谱、清晰、真实、可用、不罗嗦版)
  14. 轻重搭配|计蒜客2019蓝桥杯省赛 B 组模拟赛(一)
  15. 20145317 网络对抗技术 逆向与Bof基础
  16. chromedriver下载安装
  17. nyoj Registration system
  18. hdu 5007
  19. 20155207王雪纯 Exp2 后门原理与实践
  20. IEEE Bigger系列题解

热门文章

  1. hdoj--3594--Cactus(tarjan)
  2. 【转】iOS多语言本地化(国际化)设置
  3. [jzoj 5662] 尺树寸泓 解题报告 (线段树+中序遍历)
  4. No changes detected or App &#39;blog&#39; could not be found. Is it in INSTALLED_APPS?
  5. 为IT程序员量身定制的12个目标——很经典
  6. sql server 清理数据库日志
  7. C++代码审查---参考林锐高质量C/C++
  8. IDEA里面的facets和artifacts的讲解
  9. Java 实现简单的RPC框架
  10. ntp.log日志梳理