考虑对棋盘染色.
行加列为奇数的为白色,剩下的为黑色
发现一个白色的棋子能攻击到的一定是黑色.
符合二分图,之后连边.
要求放最多的棋子,也就是说在二分图中选最多的点使得他们没有边.
最大独立集=n-最小顶点覆盖=n-最大匹配
伪证：选出最多的点没有边==n-选出最少的点覆盖所有边==n-最大匹配
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=210; int link[N*N],tot,n,m,T,id,vis[N*N],ans,match[N*N]; int dx[8]={-2,-2,-1,1,2,2,1,-1},dy[8]={-1,1,2,2,1,-1,-2,-2}; bool f[N][N]; struct edge{int y,next;}a[N*N]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline void add(int x,int y) { a[++tot].y=y; a[tot].next=link[x]; link[x]=tot; } inline bool dfs(int x) { for(int i=link[x];i;i=a[i].next) { int y=a[i].y; if(vis[y]!=id) { vis[y]=id; if(!match[y]||dfs(match[y])) {match[y]=x;return true;} } } return false; } int main() { //freopen("1.in","r",stdin); n=read();m=read();T=read(); for(int i=1;i<=T;++i) { int x=read(),y=read(); f[x][y]=1; } for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { if(!f[i][j]&&(i+j)%2==0) { for(int k=0;k<8;++k) { int x=i+dx[k],y=j+dy[k]; if(x>=1&&x<=n&&y>=1&&y<=m&&!f[x][y]) add((i-1)*m+j,(x-1)*m+y); } } } for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(!f[i][j]&&(i+j)%2==0) { ++id; if(dfs((i-1)*m+j)) ans++; } printf("%d",n*m-T-ans); return 0; }