[luogu 3355] 骑士共存问题 {匈牙利算法} help!!!

news/2024/2/28 1:04:37

题目

https://www.luogu.org/problemnew/show/P3355#sub


解题思路

这道题自从上一次得了90分后,就一直搁置了很久,找不到错误。请各位大佬帮忙!!!


代码匈牙利算法

#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int b[8]={-2,-1,1,2,2,1,-1,-2},c[8]={1,2,2,1,-1,-2,-2,-1};
struct node{int y,next;}a[320032]; 
int rr,ans,sum,add,n,m,xx,yy,link[40001],v[40001],list[40001],t[201][201];
inline int read()
{int f=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) f=(f<<3)+(f<<1)+c-48,c=getchar();return f;
}
void write(int x){if (x>9) write(x/10); putchar(x%10+48);}
inline bool find (int q){for (register int i=list[q];i;i=a[i].next)if (!v[a[i].y]){v[a[i].y]=1; int u=link[a[i].y]; link[a[i].y]=q; if (!u||find(u)) return 1; link[a[i].y]=u; }	return 0;
}
signed main()
{n=read(); m=read();  ans=n*n-m; for (register int i=1;i<=m;i++) t[(xx=read())][(yy=read())]=-1; for (register int i=1;i<=n;i++)for (register int j=1;j<=n;j++)if (!t[i][j]&&((i+j)&1)){t[i][j]=++add;for (register int k=0;k<8;k++){xx=i+b[k]; yy=j+c[k];if ((xx>=1&&xx<=n)&&(yy>=1&&yy<=n)){if (!t[xx][yy]) t[xx][yy]=++rr; if (t[xx][yy]!=-1) a[++sum].y=t[xx][yy],a[sum].next=list[add],list[add]=sum; }}}for (register int i=1;i<=add;i++){memset(v,0,sizeof(v));if (find(i)) ans--; }write(ans); return 0; 
}

http://www.ppmy.cn/news/218472.html

相关文章

bzoj3355[Usaco2004 Jan]有序奶牛*

bzoj3355[Usaco2004 Jan]有序奶牛 题意&#xff1a; 约翰的N头牛排成一行挤奶时&#xff0c;有确定的顺序。他拥有L条关于奶牛顺序的信息&#xff0c;所有的信息都写成“A在B的前面”这样的形式。请帮助约翰删除尽可能多的冗余信息&#xff0c;但要保证能推出原有的顺序。n≤15…

洛谷 [P3355] 骑士共存问题

二分图求最大独立点集 本问题在二分图中已处理过,此处用dinic写了一遍 #include <iostream> #include <cstdio> #include <algorithm> #include <cstdlib> #include <queue> #include <cstring> using namespace std; const int MAXN40005…

洛谷P3355 骑士共存问题

题目描述 在一个 n*n个方格的国际象棋棋盘上&#xff0c;马&#xff08;骑士&#xff09;可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍&#xff0c;骑士不得进入 对于给定的 n*n 个方格的国际象棋棋盘和障碍标志&#xff0c;计算棋盘上最多可以放置多少个骑士&#x…

lugou P3355 骑士共存问题

题面传送门 显然是二分图建模板子题。 观察可得&#xff0c;可以黑白染色建图。 那么从黑格向白格建边跑二分图最小点覆盖即可&#xff0c;注意要用全部点减去最小点覆盖。 代码实现: #include<cstdio> #include<cstring> #include<queue> #define min(a,b)…

洛谷_3355_网络流/最大匹配

题目&#xff1a; 题目描述 在一个 n*n个方格的国际象棋棋盘上&#xff0c;马&#xff08;骑士&#xff09;可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍&#xff0c;骑士不得进入 对于给定的 n*n 个方格的国际象棋棋盘和障碍标志&#xff0c;计算棋盘上最多可以放置…

洛谷 P3355 骑士共存问题

题面 题意 给出一张边长为n,有几个障碍点的棋盘,问最多可以放几个骑士使他们不互相攻击. 做法 我们可以反过来考虑,先将棋盘放满骑士,计算至少去掉几个骑士. 经过观察,我们可以发现,相同颜色的格子上的棋子无法相互攻击,因此可以让超级源点连想每一个红点,每一个黄点连向超…

Luogu P3355 骑士共存问题

题目链接 \(Click\) \(Here\) 二分图最大独立集。对任意两个可以相互攻击的点&#xff0c;我们可以选其中一个。对于不会互相攻击的&#xff0c;可以全部选中。所以我们只需要求出最大匹配&#xff0c;根据定理&#xff0c;二分图最大独立集等于点数减去最大匹配&#xff0c;就…

[P3355骑士共存]

P3355 方格里面选若干个点放上骑士&#xff0c;骑士之间不能互相攻击到。问最多能放多少骑士。emm。可能是被费用流整自闭了&#xff0c;还以为这道题也是个神题&#xff0c;在想怎么用费用流跑。看了一下自己之前居然写过这道题&#xff0c;代码居然是匈牙利&#xff1f;&…

[Python3] 爬取百度图片到本地

前言 因为需要一些图片素材&#xff0c;又不想一个个手动下载&#xff0c;遂通过爬虫来解放双手。在百度图片中搜索“汉服美女”&#xff0c;然后以浏览器地址栏上的地址作为初始 URL。通过对 URL 分析知道 URL 分为 3 部分&#xff1a;域名 固定参数 关键字参数。 爬取 #…

P3355 骑士共存问题

题目描述 在一个 n*n个方格的国际象棋棋盘上&#xff0c;马&#xff08;骑士&#xff09;可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍&#xff0c;骑士不得进入 对于给定的 n*n 个方格的国际象棋棋盘和障碍标志&#xff0c;计算棋盘上最多可以放置多少个骑士&…

BZOJ3355

3355: [Usaco2004 Jan]有序奶牛 Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 37 Solved: 19[Submit][Status][Discuss] Description 约翰的N(1≤N≤1500)头牛排成一行挤奶时&#xff0c;有确定的顺序&#xff0e;牛被编成连续的号码1&#xff0e;.N,他拥有L条关于奶牛顺…

笔记本外接显示器,R7000

618新买了个显示器,2K的&#xff0c;笔记本是联想的R7000&#xff1b; 能正常使用&#xff0c;使用HDMI接口2.0的线(线的话应该无所谓)&#xff0c;显示器能正常使用不过只能开到144HZ,更高的就不行了&#xff0c;显示器就不支持了&#xff0c;虽然显示器有DP1.4的接口但笔记本…

刷新率属于计算机的显示性能指标吗,显示器性能指标(菜鸟必看)

显示器性能指标 1、显像管的尺寸&#xff1a;就是我们通常所说的14、15、17英寸&#xff0c;注意&#xff0c;这里说的长度是指显示器屏幕对角线的长度&#xff0c;单位为英寸(1英寸25.4毫米)。虽然显示器通常用15英寸、17英寸这样的指标来衡量屏幕大小&#xff0c;实际上它们的…

设置计算机屏幕设置摇摆式,吃鸡画质怎么调最舒服?关键是在显示器上

吃鸡画质怎么调最舒服&#xff1f;主要是显示器&#xff0c;吃鸡这款游戏&#xff0c;因为优化原因&#xff0c;本身FPS不会很高&#xff0c;所以从帧率来说&#xff0c;现在大部分144Hz的电竞显示器就足够了&#xff0c;但在这之外&#xff0c;很多电竞显示器还针对各种游戏做…

计算机显示屏知识,显示器基础知识:通俗易懂的台式电脑显示器知识(2)

关于使用场景 吃鸡、CS go、CF等射击类游戏玩家&#xff1a; 在你的显卡足够强大的情况下(也就是游戏帧数FPS大于60帧)&#xff0c;这类用户选择144hz刷新、1ms延迟的显示器是很有必要的。144hz流畅顺滑的画面不仅能在左右转屏时看清敌人&#xff0c;也能减轻游戏时因为卡顿带来…

wx.checkjsapi 一直显示ok_大聪明的显示器推荐

此篇显示器推荐&#xff0c;是为了配合我自己的电脑配置推荐来的。同样充满了个人喜好。仅推荐IPS显示器。对电脑配置有需求的可以私信 大聪明&#xff1a;我的2020年台式电脑主机配置推荐​zhuanlan.zhihu.com 以后显示器都在这里推荐了。为了让原文章更清楚明白一点&#xff…

进去springstrap显示无响应_勉强算是比较详细的游戏显示器推荐

题图&#xff0c;南瓜车资深管理&#xff0c;汤圆女神。 据说颜值和歌声不输给二珂&#xff0c;可以说各擅胜场&#xff0c;但是可以肯定的是&#xff0c;汤圆说话的声音是真的好听&#xff0c;远胜二珂。二珂出席活动的讲话可以在网上找到&#xff1b;至于汤圆的&#xff0c;还…

新时达服务器的显示板坏了,液晶显示器驱动板几种常见故障的检修

公告: 为响应国家净网行动,部分内容已经删除,感谢读者理解。 话题:液晶显示器驱动板几种常见故障的检修推荐回答:,有时处理芯片坏了温度很高,颜色不正常,然后用万用表测量,电容不良.3v)电压的提供。如果用通用板测试正常,刷程序等等了,电容,那么按键板上的各个按键…

什么是CRT显示器技术

现在显示器无处不在&#xff0c;它的应用也十分广泛&#xff0c;显示器的发展一直都是整个IT行业发展大家所关注的焦点&#xff0c;每当显示器有了革命产品出现往往都会为IT业带来一阵风暴与热潮。回想起2001年显示器产业的发展过程&#xff0c;纯平CRT与LCD液晶显示器可以说进…

台式计算机不显示,台式电脑开机显示器不显示怎么办

可能还有些网友不太了解台式电脑开机显示器不显示的情况,下面就由学习啦小编给你们介绍台式电脑开机显示器不显示的解决方法吧,希望能帮到大家哦! 台式电脑开机显示器不显示的解决方法: 1.首先我们要检查一下显示器的电源有没有插上,电源有没有打开,这个方面估计有很多人犯…
最新文章