原题链接：https://www.luogu.org/problemnew/show/P3355
事前声明:这不是一份题解，而是一次真正的做题记录，题解反而是次要的。。。
所出现的错误均已加入《GG记录》:http://www.cnblogs.com/zeroform/p/7678669.html
题意简述：n*n的方阵中，有m个障碍点，不能放骑士，求一种方案，能放下最多的骑士，使他们互不攻击。
显然，黑格的骑士只能攻击到白格，白格的骑士只能攻击到黑格，至于障碍点，当它不存在过就好了。
然后，这就转化为了一个点控制其他点，求最多能取几个点的问题。
我已经做过方格取数问题（https://www.luogu.org/problemnew/show/P2774）啦，源点向所有黑点连一条边，流量为1，所有白点向汇点连一条边，流量为1，每个黑点向它能控制的白点连一条边，流量无限大。建完图跑个最小割，这样就能保证所有骑士互不攻击了，最后拿总点数减去障碍点数再减去最小割就好啦，这个题流量还只有1和无限大，不久数据范围大点嘛，网络流的时间复杂度不是O（跑得过）吗？（滑稽）。
然后。。。
AC WA TLE RE都有。。。exm？
冷静地观察了一下，哦，把方阵当成n*m的了，怪不得静态差错没看出来，没关系，再来一次。
只有54分，唔。。。有个i和j敲反了。。。手贱。。。。这次应该能AC了吧
81分，T了两个点，O2优化也没半点用，嗯。。。看来dinic太慢了，换ISAP！
然而看讨论的时候dalao说dinic有优化，赶快去增长姿势。
woc！弧优化的dinic跑过ISAP了，玄学！（其实并不）
总之AC了，上代码吧。
#include<cstdio> #include<queue> #include<cstring> #include<iostream> using namespace std; const int inf=(1<<30); const int t=50001; void read(int &y) { y=0;char x=getchar(); while(x<'0'||x>'9') x=getchar(); while(x>='0'&&x<='9') { y=y*10+x-'0'; x=getchar(); } } int nx[8]={-2,-2,-1,-1,1,1,2,2}; int ny[8]={-1,1,-2,2,-2,2,-1,1}; int n,m,a[205][205],zx,zy,cnt=1; struct edge { int u,v,w; }e[500003]; int head[50003],dis[50003]; void add(int x,int y,int z) { e[++cnt].u=head[x];e[cnt].v=y; e[cnt].w=z;head[x]=cnt; e[++cnt].u=head[y];e[cnt].v=x; e[cnt].w=0;head[y]=cnt; } int dfs(int x,int f) { if(x==t) return f; int d,tmp=0; for(int i=head[x];i!=-1;i=e[i].u) { int nxt=e[i].v; if(dis[nxt]==dis[x]+1&&e[i].w>0&&(d=dfs(nxt,min(f-tmp,e[i].w)))) { e[i].w-=d; e[i^1].w+=d; tmp+=d; if(tmp==f) return tmp; } } if(!tmp) dis[x]=0; return tmp; } int bfs() { memset(dis,0,sizeof(dis)); queue<int>q; q.push(0);dis[0]=1; while(!q.empty()) { int tmp=q.front();q.pop(); for(register int i=head[tmp];i!=-1;i=e[i].u) { int p=e[i].v; if(dis[p]||e[i].w<=0) continue; dis[p]=dis[tmp]+1; q.push(p); } } return dis[t]; } int dinic() { int re=0; while(bfs()) re+=dfs(0,inf); return re; } int main() { memset(head,-1,sizeof(head)); read(n);read(m); for(int i=1;i<=m;i++) { read(zx);read(zy); a[zx][zy]=1; } for(register int i=1;i<=n;i++) { for(register int j=1;j<=n;j++) { if(a[i][j]==1) continue; if((i+j)%2==0) { add(0,i*n+j,1); for(register int k=0;k<8;k++) { int tx=i+nx[k]; int ty=j+ny[k]; if(tx<1||tx>n||ty<1||ty>n) continue; if(a[tx][ty]==0) add(i*n+j,tx*n+ty,inf); } } else add(i*n+j,t,1); } } printf("%d",n*n-m-dinic()); return 0; }