BZOJ4808马——二分图最大独立集
发布日期:2021-08-26 18:18:27 浏览次数:51 分类:技术文章

本文共 1348 字,大约阅读时间需要 4 分钟。

题目描述

众所周知,马后炮是中国象棋中很厉害的一招必杀技。"马走日字"。本来,如果在要去的方向有别的棋子挡住(俗
称"蹩马腿"),则不允许走过去。为了简化问题,我们不考虑这一点。马跟马显然不能在一起打起来,于是rly在
一天再次借来了许多许多的马在棋盘上摆了起来……但这次,他实在没兴趣算方案数了,所以他只想知道在N×M的
矩形方格中摆马使其互不吃到的情况下的最多个数。但是,有一个很不幸的消息,rly由于玩得太Happy,质量本来
就不好的棋盘被rly弄坏了,不过幸好只是破了其中的一些格子(即不能再放子了),问题还是可以继续解决的。

输入

一行,两个正整数N和M。
接下来N行,每行M个数,要么为0,表示没坏,要么为1,表示坏了。
N<=200,M<=200

输出

一行,输出最多的个数。

样例输入

2 3
0 1 0
0 1 0

样例输出

2
 
 
  这道题和是一样的题,黑白染色之后跑二分图最大匹配,用矩阵大小-1的数目-二分图最大匹配数。
#include
#include
#include
#include
#include
using namespace std;int next[1000001];int to[1000001];int val[1000001];int head[1000001];int tot=1;int q[1000001];int n,k,m;int S,T;int ans;int x,y;int d[1000001];int c[1001][1001];const int dx[]={-2,-1,1,2,2,1,-1,-2};const int dy[]={1,2,2,1,-1,-2,-2,-1};void add(int x,int y,int v){ tot++; next[tot]=head[x]; head[x]=tot; to[tot]=y; val[tot]=v; tot++; next[tot]=head[y]; head[y]=tot; to[tot]=x; val[tot]=0;} bool bfs(int S,int T){ int r=0; int l=0; memset(q,0,sizeof(q)); memset(d,-1,sizeof(d)); q[r++]=S; d[S]=0; while(l
0&&fx<=n&&fy>0&&fy<=m&&c[fx][fy]!=-1) { add(c[i][j],c[fx][fy],0x3f3f3f); } } } } } dinic(); printf("%d",n*m-k-ans);}

转载于:https://www.cnblogs.com/Khada-Jhin/p/9301740.html

转载地址:https://blog.csdn.net/weixin_33894640/article/details/92657377 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Log4j 1使用教程
下一篇:Flash游戏抓取,flash网站抓取,网页游戏提取工具

发表评论

最新留言

逛到本站,mark一下
[***.202.152.39]2024年03月21日 09时58分04秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

唱好铁血丹心谐音正规_趙贤典:打好“感情牌” 唱好“大合唱” 2019-04-21
aix系统vi修改命令_Linux基础知识必备:利用vi编辑器创建和编辑正文文件 2019-04-21
天涯明月刀开发_玩家被天涯明月刀手游“冷落”?六大门派角色竟不带正眼看人... 2019-04-21
this指向undefined uiapp_一个this都没有,真好 2019-04-21
add p4 多个文件_2-3【微信小程序全栈开发课程】index页面完善--vue文件代码解析... 2019-04-21
5w2h原则指的是什么_什么是5W2H分析法?一首小诗带入进入大门。 2019-04-21
技校毕业是什么学历_中等职业学校是什么_中等职业学校毕业是什么学历 2019-04-21
2压缩备份数据库_MySQL数据备份与恢复(二) xtrabackup工具 2019-04-21
英特尔cpu发布时间表_被嘲讽的英特尔核显,强大能力其实超乎你的想象 2019-04-21
chi2inv函数 matlab_MATLAB概率和统计(2) 2019-04-21
lisp修改上一个图素_在Windows上安装Haskell 2019-04-21
ad19 导出step 没有pcb_几款主流PCB软件哪个最好用,你用过几款? 2019-04-21
json mysql 字段 默认值_Newtonsoft.Json 六个超简单又实用的特性,值得一试 【上篇】... 2019-04-21
ocdma相干非相干_《Acconeer 60GHz脉冲相干雷达芯片:A111》 2019-04-21
修改表格字体颜色_Excel技巧:Excel如何修改字体颜色 2019-04-21
native react 变颜色 点击_React Native主动更改StackNavigator标头颜色 2019-04-21
prism项目搭建 wpf_WPF MVVM使用prism4.1搭建 2019-04-21
python发微信红包群_用Python实现微信自动化抢红包,再也不用担心抢不到红包了... 2019-04-21
python中func自定义函数_Python函数之自定义函数&作用域&闭包 2019-04-21
wget连接指定端口_端口通不通 telnet wget ssh 2019-04-21