骑士共存问题
«问题描述：
在一个n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘
上某些方格设置了障碍，骑士不得进入。
«编程任务：
对于给定的n*n个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑
士，使得它们彼此互不攻击。
«数据输入：
由文件knight.in给出输入数据。第一行有2 个正整数n 和m (1<=n<=200, 0<=m<=n*n)<n2)，< span="">
分别表示棋盘的大小和障碍数。接下来的m 行给出障碍的位置。每行2 个正整数，表示障
碍的方格坐标。
«结果输出:
将计算出的共存骑士数输出到文件knight.out。
输入文件示例 输出文件示例
knight.in
3 2
1 1
3 3
knight.out
5
/* 观察题目，我们可以知道，能够互相跳到的两个点颜色（棋盘颜色）一定是不同的，所以进行染色建一个二分图， 接下来再跑最大独立集。 最大独立集=V-最大匹配。 PS：我的dinic又被虐了，以后真的要改dinic的写法了。 */ #include<cstdio> #include<iostream> #define N 40010 #define M 10000010 #define inf 1000000000 using namespace std; int a[210][210],head[N],dis[N],q[N],n,m,cnt=1,S,T; int dx[8]={1,1,-1,-1,2,2,-2,-2}; int dy[8]={2,-2,2,-2,1,-1,1,-1}; struct node{ int v,pre,f; };node e[M]; int ws(int x,int y){ return (x-1)*n+y; } void add(int u,int v,int f){ e[++cnt].v=v;e[cnt].f=f;e[cnt].pre=head[u];head[u]=cnt; e[++cnt].v=u;e[cnt].f=0;e[cnt].pre=head[v];head[v]=cnt; } bool bfs(){ for(int i=1;i<=T;i++)dis[i]=inf; int h=0,t=1;q[1]=S;dis[S]=0; while(h<t){ int now=q[++h]; for(int i=head[now];i;i=e[i].pre){ int v=e[i].v; if(e[i].f&&dis[v]>dis[now]+1){ dis[v]=dis[now]+1; if(v==T)return true; q[++t]=v; } } } return dis[T]!=inf; } int dinic(int now,int f){ if(now==T)return f; int w,used=0; for(int i=head[now];i;i=e[i].pre){ int v=e[i].v; if(e[i].f&&dis[v]==dis[now]+1){ w=f-used; w=dinic(e[i].v,min(e[i].f,w)); e[i].f-=w; e[i^1].f+=w; used+=w; if(used==f)return f; } } if(!used) dis[now]=-1; return used; } int main(){ freopen("knight.in","r",stdin); freopen("knight.out","w",stdout); scanf("%d%d",&n,&m); S=0;T=n*n+1; for(int i=1;i<=m;i++){ int x,y;scanf("%d%d",&x,&y); a[x][y]=1; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ if(a[i][j])continue; if(i+j&1) add(ws(i,j),T,1); else add(S,ws(i,j),1); } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ if(i+j&1) continue; for(int k=0;k<8;k++){ int x=i+dx[k],y=j+dy[k]; if(x>=1&&x<=n&&y>=1&&y<=n&&!a[x][y]) add(ws(i,j),ws(x,y),1); } } int ans=n*n-m; while(bfs()) ans-=dinic(S,inf); printf("%d",ans); return 0; }