「Luogu3355」 骑士共存问题
Solution
二分图最大点独立集问题
首先对棋盘黑白染色
从所有无障碍的黑点向能攻击到的无障碍的白点连边
按照二分图最大点独立集=二分图最大匹配，跑二分图匹配即可
Code
#include#include #include #include #include #include #define maxn 205#define maxm 40005using namespace std;typedef long long ll;template void read(T &t){ t=0;char c=getchar();int f=0; while(!isdigit(c)){f|=c=='-';c=getchar();} while(isdigit(c)){t=t*10+c-'0';c=getchar();} if(f)t=-t;}int n,m;int ocr[maxm];int ans;struct edge{ int u,v,nxt;}g[maxm*4];int head[maxm],ecnt;void eADD(int u,int v){ g[++ecnt].u=u; g[ecnt].v=v; g[ecnt].nxt=head[u]; head[u]=ecnt;}inline int trans(int x,int y){ return (x-1)*n+y;}int result[maxm],use[maxm],sign;bool Hungary(int u){ for(register int i=head[u];i;i=g[i].nxt) { int v=g[i].v; if(use[v]==sign) continue; use[v]=sign; if(!result[v] || Hungary(result[v])) { result[v]=u; return true; } } return false;}void Calc(){ for(register int i=1;i<=n;++i) for(register int j=1;j<=n;++j) if(!ocr[trans(i,j)] && (i+j)&1) { sign=trans(i,j); ans+=Hungary(trans(i,j)); }}const int dx[8]={-2,-2,-1,-1,1,1,2,2},dy[8]={-1,1,-2,2,-2,2,-1,1};int main(){ read(n),read(m); for(register int i=1;i<=m;++i) { int x,y; read(x),read(y); ocr[trans(x,y)]=1; } for(register int i=1;i<=n;++i) for(register int j=1;j<=n;++j) if(!ocr[trans(i,j)] && (i+j)&1) for(register int k=0;k<8;++k) { int X=i+dx[k],Y=j+dy[k]; if(X<1 || X>n || Y<1 || Y>n || ocr[trans(X,Y)]) continue; eADD(trans(i,j),trans(X,Y)); } Calc(); printf("%d",n*n-m-ans); return 0;}