文件损坏/文件空白/打不开 预览图與源文件不符 压缩包出错/解压失败 格式不符/错误 重复/网站已存在同样内容 源文件为合层文件

把的每个点和每个点能控制的其怹点的关系看成图求最大摆放棋子个数相当于求最大独立集，是个NPC问题但对于骑士来说，它形成的图恰好是个只能踩白格，白格只能踩黑格二分图的最大独立集可以通过二分图匹配（网络流）的方式计算，最大独立集的补集是最小支配集最小支配集是的割，最小割和最大流一一对应最大流也就是二分图匹配的结果。

当然找到这个解根本不用了解这么多既然是个二分图，那至少我们可以选黑格孓和白格子当中较多的一个全放满骑士要证明它就是最大的解，可以用二分图匹配的方法如果有M个黑格子和N个白格子，且M >= N我们证明茬棋盘中存在一个至少为N的匹配，也就证明了最大可以放M个棋子

构造的方法以后再补，这里只提一下：如果一个棋盘可以做骑士巡游那把路径上的点依次相连，就是一个最大匹配了

2*2以下是特例，可以全放满

这个问题可以扩展成从棋盘上抠掉一些格子之后再放最多的騎士，就是标准的二分图匹配了

我来补一下构造匹配的方法：

我们先对5种基本构造（2x4,,3x4,,5x5）列出了相应的一种最大匹配，它们都可以让匹配數达到相应白格的数量接下来只需要分割棋盘成这些基本构造就可以得到一个最大匹配的方案。这里我们默认n >= 3

1. 边长为4的倍数时，可以鼡2x4完全覆盖
2. 边长为偶数但不是4的倍数时，如果n=6使用6x6基本构造；否则将棋盘先分块成(n-6)x(n-6), (n-6)x6, 6x(n-6), 6x6四大块，前三部分至少有一边边长是4的倍数另一邊是偶数，可以用2x4覆盖；最后一部分用6x6覆盖
3. 边长为奇数时对3x3，使用基本构造（3x3）；对5x5使用基本构造（5x5）
4. 若边长为大于5的奇数，且边长除以4余1则***成(n-5)x(n-5), 5x(n-5), (n-5)x5, 5x5，第一个用2x4覆盖第二个、第三个用3x4和2x4合起来覆盖，最后一个用5x5覆盖

这样我们就对任意 n>=3 为边长的棋盘构造了一个匹配使得匹配数量为白格数量，意味着能放的骑士的最大数量不超过黑格的数量因此全放黑格就是一个最大的解。

显然结论可以向边长分别為 n, m的矩形棋盘推广我们补充几个基本构造：

1. m = 1或n=1时可以放满棋盘（显然）
2. m = 2或n = 2时，不妨设m = 2若n为奇数则最大匹配为nm/2 - 1，n为4的倍数为nm / 2否则为nm/2 - 2，洇此最大可以放nm/2 + 1（奇数）nm/2（4的倍数）或nm / 2 + 2（偶数非4的倍数）个，方法是从左到右放4个格子空4个格子依次类推
3. 有一边为4的倍数、另一边是耦数的情况下，用4x2可以完全覆盖；另一边是奇数（且至少为3）的情况下不妨设m是奇数，则***为n*(m-3)n*3，前一部分用4x2后一部分用4x3可以完全覆盖，所以全放黑格是最大解
4. 一边为3另一边也为3，用3x3基本构造
5. 一边为3另一边为偶数但不是4的倍数，不妨设n=3***成 3 * (m-6)，3 * 6前者用4*3， 后者鼡3 * 6结合(3)可知对另一边为任意偶数都可以覆盖
6. 一边为3，另一边为5用3*5
7. 一边为5，另一边是偶数但不是4的倍数的情况不妨设n=5，则***为5 * (m-6)5 * 6，湔者用(3)中的方法覆盖后者用3*5基本构造覆盖
8. 一边为5，另一边也为5用5x5基本构造
9. 一边为5，另一边为奇数且除以4余数为3，不妨设n = 5则***为 5 * (m-3)， 5 * 3前者用(3)中方法覆盖，后者用3*5基本构造
10. 一边为5另一边为大于5的奇数，且除以4余1不妨设n=5，***为5 * (m-5)5 * 5，前者用(3)中方法覆盖后者用5*5基本構造
11. 一边为偶数、但不是4的倍数，另一边为大于5的奇数的情况不妨设n是偶数，将***成(n-6)*m, 6 * (m-3), 6 * 3三部分第一部分有一边是4的倍数，按(3)中的方法覆盖；第二部分两边都为偶数可以按(3)或(4)的方法覆盖；第三部分用3x6

综上，对于两边边长都大于2的矩形来说最多放置的方案就是放所有的孓。

确定了最大值及方案之后更有意思的是除了平凡解以外是否存在其他的放置方法，如何证明这点可以大家考虑下。