题目名称	746. [网络流24题] 骑士共存
输入输出	`knight.in/out`
难度等级	★★★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	Makazeu 于2012-04-05加入
开放分组	全部用户
提交状态
分类标签	二分图网络流黑白染色
查看题解	分享题解

通过：265，提交：949，通过率：27.92%
冷曦	100	0.102 s	10.26 MiB	C++
‎MistyEye	100	0.137 s	3.55 MiB	C++
一個人的雨	100	0.140 s	4.93 MiB	C++
NPK	100	0.163 s	2.14 MiB	C++
NPK	100	0.165 s	2.14 MiB	C++
TargetLocked	100	0.169 s	21.19 MiB	C++
卜卜	100	0.174 s	2.45 MiB	C++
再见	100	0.179 s	4.73 MiB	C++
liu_runda	100	0.182 s	4.59 MiB	C++
Ezoi_XY	100	0.189 s	3.23 MiB	C++

关于骑士共存的近10条评论(全部评论)
匈牙利的确做不了 ┭┮﹏┭┮ 2024-01-12 18:59 26楼
回复 @沉迷学习的假��Keller : 大佬，大白书？发光二向箔 2020-01-20 11:54 25楼
第一次被卡常70 +读入优化80，第三个点本地数分钟算不出结果。 +当前弧优化AC。原来这个优化这么强... sxysxy 2017-03-31 09:49 24楼
回复 @Rapiz : 什么鬼 ..... 卜卜 2017-03-06 16:18 23楼
200×200=5000 Rapiz 2017-03-06 13:00 22楼
求助啊。。。我写的isap死活过不了，有什么优化吗？找到优化了。。。其实没必要对于每个格子各自拆点其实这个矩阵本身就是一个二分图。。。虽然我还是比较慢啊。。。 ztzshiwo 2017-02-17 20:08 21楼
不枉我调了两个小时，发现一个超级大优化，以后不怕怕了 New World 2017-01-05 21:01 20楼
时至今日终于把心头大恨切了...... 以为标号奇偶性可以判定是在二分图的哪一边...感觉自己好智障...... AntiLeaf 2016-11-12 08:58 19楼
忘了初始化指针为-1 尼玛T了9个调了那么久！！！QAQ 安呐一条小咸鱼。 2016-06-16 11:57 18楼
邻接矩阵会超内存超的很惨::>_<:: _Itachi 2016-06-13 19:26 17楼

746. [网络流24题] 骑士共存

★★★☆ 输入文件：knight.in 输出文件：knight.out 简单对比
时间限制：1 s 内存限制：128 MiB

骑士共存问题
«问题描述：
在一个n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘

上某些方格设置了障碍，骑士不得进入。

«编程任务：
对于给定的n*n个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑
士，使得它们彼此互不攻击。
«数据输入：
由文件knight.in给出输入数据。第一行有2 个正整数n 和m (1<=n<=200, 0<=m<=n*n)
分别表示棋盘的大小和障碍数。接下来的m 行给出障碍的位置。每行2 个正整数，表示障
碍的方格坐标。
«结果输出:
将计算出的共存骑士数输出到文件knight.out。
输入文件示例输出文件示例
knight.in
3 2
1 1

3 3

knight.out