骑士放置——匈牙利算法的应用

前置芝士：二分图最大匹配。

题意已经很明了了，唯一需要注意的点是能相互攻击是指能一步到达。

这题有点像“八皇后”，因此我们先想到暴搜

所以——众所周知，暴搜是过不去的，因此我们索性画个图。

这就是国际象棋的棋盘（好吧不是我画的）

我们把每个可以一步到达的格子连起来（作者因为手懒，只连了大约 $15$ 条）

我们发现作者的手懒是有道理的，因为我们已经找到规律了：两个可以互相攻击到的马，一定一个在黑格，一个在白格。 仔细看看每条边是不是都是这样？

那么，如果把边连全，我们就得到了一张二分图，我们的任务就是选最多的点，满足两两之间没有边相连，也就是最大独立集。在二分图中，最大独立集 $=$ 点数 $-$ 最小点覆盖。

最小点覆盖指选最少的点，满足每条边至少有一个端点被选，而根据 König 定理，在二分图中，最小点覆盖 $=$ 最大匹配。那么，我们就可以用匈牙利算法解决这道题了。

代码供参考：

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int N=5e4+5;
vector<int> To[N];
int mtc[N];
bool st[N],Fire[N];
int dx[9]={0,1,1,-1,-1,2,2,-2,-2},dy[9]={0,-2,2,-2,2,-1,1,-1,1};
int n,m,T,ans;
int id(int x,int y){return (x-1)*m+y;}
bool akioi(int tnsh1,int tnsh2){
	return !(tnsh1<1||tnsh1>n||tnsh2<1||tnsh2>m||Fire[id(tnsh1,tnsh2)]);
}
bool fnd(int u)
{
	for(int i=0;i<To[u].size();i++){
		int v=To[u][i];
		if(!st[v]){
			st[v]=1;
			if(mtc[v]==0||fnd(mtc[v])){
				mtc[v]=u;
				return true;
			}
		}
	}
	return false;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m>>T;
	for(int i=1;i<=T;i++)
	{
		int x,y;
		cin>>x>>y;
		Fire[id(x,y)]=true;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(Fire[id(i,j)]||!((i&1)==(j&1))) continue;
			for(int k=1;k<=8;k++)
				if(akioi(i+dx[k],j+dy[k]))
					To[id(i,j)].push_back(id(i+dx[k],j+dy[k]));
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(Fire[id(i,j)]||!((i&1)==(j&1))) continue;
			memset(st,0,sizeof st);
			if(fnd(id(i,j))) ans++;
		}
	}
	cout<<n*m-T-ans;
	return 0;
}

望管理大大给过QwQ~