题目：洛谷P3355、codevs1922。
题目大意：在n*n的国际象棋棋盘上，有一些障碍点，这些障碍点不能放任何东西。现在要在棋盘没障碍的地方放置骑士（马），问最多能放多少个，使它们不互相攻击？
解题思路：最小割问题。
此题同“方格取数问题”思路相同。
由于马攻击到的点和它所在点的颜色必然不相同，那么我们将棋盘黑白染色，黑的连源点，白的连汇点，容量1。然后黑点连接能攻击到的白点，容量无穷大。
如果是障碍点，则不连边。
最后求最大流，再用总数减去障碍数减去最大流即可。
注意数组开够。
C++ Code：
#include<cstdio>
#include<cstring>
#include<queue>
#define inf 0x3fffffff
std::queue<int>q;
int n,m,cnt=-1,head[70005],iter[70005],level[70005];
bool b[205][205];
int dx[]={0,2,1,-2,1,2,-1,-2,-1},
dy[]={0,1,2,1,-2,-1,2,-1,-2};
struct edge{
int to,cap,nxt;
}e[40005*10];
inline int number(int x,int y){
return(x-1)*n+y;
}
inline void addedge(int from,int to,int flow){
++cnt;
e[cnt]=(edge){to,flow,head[from]};
head[from]=cnt;
++cnt;
e[cnt]=(edge){from,0,head[to]};
head[to]=cnt;
}
void bfs(int s){
level[s]=1;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=e[i].nxt)
if(e[i].cap&&level[e[i].to]==-1){
level[e[i].to]=level[u]+1;
q.push(e[i].to);
}
}
}
int dfs(int u,int t,int f){
if(u==t)return f;
for(int& i=iter[u];i!=-1;i=e[i].nxt)
if(e[i].cap&&level[u]<level[e[i].to]){
int d=dfs(e[i].to,t,e[i].cap>f?f:e[i].cap);
if(d){
e[i].cap-=d;
e[i^1].cap+=d;
return d;
}
}
return 0;
}
int maxflow(int s,int t){
for(int flow=0;;){
memset(level,-1,sizeof level);
bfs(s);
if(level[t]==-1)return flow;
memcpy(iter,head,sizeof iter);
int f;
while(f=dfs(s,t,inf))flow+=f;
}
}
int main(){
scanf("%d%d",&n,&m);
memset(b,0,sizeof b);
for(int i=1;i<=m;++i){
int x,y;
scanf("%d%d",&x,&y);
b[x][y]=true;
}
memset(head,-1,sizeof head);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
if(b[i][j])continue;
int p=number(i,j);
if((i+j)&1){
addedge(0,p,1);
for(int h=1;h<9;++h){
int x=dx[h]+i,y=dy[h]+j;
if(x>0&&y>0&&x<=n&&y<=n&&!b[x][y])addedge(p,number(x,y),inf);
}
}else addedge(p,n*n+1,1);
}
return!printf("%d
",n*n-m-maxflow(0,n*n+1));
}