

$24.$骑士共存问题

题目

在一个 n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入

对于给定的 n*n 个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它们彼此互不攻击。

题解

我才不会说我之前一直都没用当前弧优化这次被卡才用起来的。

_{按照套路，}将图黑白染色，将白点放到$X$集合，黑点放到$Y$集合，我们知道可以相互攻击的两个点一定在不同的两个集合中，然后_按照套路将问题转化成最小割解决。

连边方式：

1. $S$向$X$集合中的没障碍的点连边容量为$1$。
2. $Y$集合中的没障碍的点向$T$连边容量为$1$。
3. 对于可以互相攻击到的两个点从一个点（假设他在$X$集合中）向另一个点（肯定在$Y$集合中）连边容量为$inf$。

所有点数减去有障碍的点数然后减去最大流就是结果。

正确性可以参考一下之前的然后稍作思考就知道了。