Description
在一个n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入。
对于给定的n*n个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它们彼此互不攻击。
Input
第一行有2 个正整数n 和m (1<=n<=200, 0<=m<=n * n)分别表示棋盘的大小和障碍数。
接下来的m 行给出障碍的位置。每行2 个正整数，表示障碍的方格坐标。
Output
将计算出的共存骑士数输出
Sample Input
3 2
1 1
3 3
Sample Output
5
正解：网络流最大独立集
解题报告：直接n^2连边，有障碍的连边容量为0，然后就跑最大流，然后用总点数-最大流-障碍数。
1 #include <iostream> 2 #include <iomanip> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <algorithm> 6 #include <cstring> 7 #include <cmath> 8 #include <string> 9 #define MIN(a,b) a<b?a:b 10 #define RG register 11 const int inf = 2147483641; 12 const int M = 50000; 13 const int N = 1000000; 14 15 using namespace std; 16 17 int gi(){ 18 char ch=getchar();int x=0; 19 while(ch<'0' || ch>'9') ch=getchar(); 20 while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); 21 return x; 22 } 23 24 int f[N],cnt=1,vis[205][205],S,T,dis[N],ans,nxt[N],head[N]; 25 int z[8]={-2,-2,-1,-1,1,1,2,2},y[8]={-1,1,-2,2,-2,2,-1,1}; 26 27 struct date{ 28 int from,to,val; 29 }nn[N]; 30 31 void link(int l,int r,int val){ 32 nn[++cnt]=(date){l,r,val},nxt[cnt]=head[l],head[l]=cnt; 33 nn[++cnt]=(date){r,l,0},nxt[cnt]=head[r],head[r]=cnt; 34 return; 35 } 36 37 int bfs(){ 38 for (RG int i=S; i<=T; ++i) dis[i]=0; 39 int l=0,r=1; 40 f[1]=0,dis[0]=1; 41 while(l<r){ 42 ++l; 43 for (RG int i=head[f[l]]; i; i=nxt[i]) 44 if (nn[i].val && dis[nn[i].to]==0){ 45 dis[nn[i].to]=dis[f[l]]+1; 46 f[++r]=nn[i].to; 47 } 48 if (dis[T]) return 1; 49 } 50 return 0; 51 } 52 53 int dinic(int xh,int sum){ 54 int s=0; 55 if (xh==T) return sum; 56 for (RG int i=head[xh]; i; i=nxt[i]) 57 if (nn[i].val && dis[nn[i].to]==dis[xh]+1){ 58 RG int tmp=dinic(nn[i].to,MIN(sum,nn[i].val)); 59 nn[i].val-=tmp,nn[i^1].val+=tmp,s+=tmp,sum-=tmp; 60 if (sum==0) break; 61 } 62 if (s==0) dis[xh]=-1; 63 return s; 64 } 65 66 int main(){ 67 freopen("x.in","r",stdin); 68 freopen("x.out","w",stdout); 69 RG int n=gi(),m=gi();T=n*n+1; 70 for (RG int i=1; i<=m; ++i){ 71 RG int l=gi(),r=gi(); 72 vis[l][r]=1; 73 } 74 for (RG int i=1; i<=n; ++i){ 75 RG int s=(i-1)*n; 76 for (RG int j=1; j<=n; ++j) 77 for (RG int k=0; k<=7; ++k) if ((i+j)&1){ 78 RG int xi=i+z[k],yi=j+y[k],g=(xi-1)*n; 79 if (xi<=n && xi>0 && yi>0 && yi<=n) 80 link(s+j,g+yi,1); 81 } 82 } 83 for (RG int i=1; i<=n; ++i){ 84 RG int s=(i-1)*n; 85 for (RG int j=1; j<=n; ++j) 86 if ((i+j)&1) 87 link(S,s+j,vis[i][j]^1); 88 else 89 link(s+j,T,vis[i][j]^1); 90 } 91 while(bfs()) 92 ans+=dinic(S,inf); 93 printf("%d",n*n-ans-m); 94 return 0; 95 }