1. [网络流24题] 骑士共存
   ★★☆ 输入文件：knight.in 输出文件：knight.out 简单对比
   时间限制：1 s 内存限制：128 MB
   骑士共存问题
   «问题描述：
   在一个n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘
   上某些方格设置了障碍，骑士不得进入。
   
   «编程任务：
   对于给定的n*n个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑
   士，使得它们彼此互不攻击。
   «数据输入：
   由文件knight.in给出输入数据。第一行有2 个正整数n 和m (1<=n<=200, 0<=m<=n*n)
   分别表示棋盘的大小和障碍数。接下来的m 行给出障碍的位置。每行2 个正整数，表示障
   碍的方格坐标。
   «结果输出:
   将计算出的共存骑士数输出到文件knight.out。
   输入文件示例 输出文件示例
   knight.in
   3 2
   1 1
   3 3
   knight.out
   5

/*最大独立集问题.跑二分图匹配.建图比较鬼畜.注意边的编号问题. ans=V-最大匹配数.dinic即可. (证明自行百度) */#include
    
     #include
     
      #include
      
       #include
       
        #define MAXN 210using namespace std;int dis[MAXN*MAXN+10],n,cut=1,ans,tot,m,max1=1e9,head[MAXN*MAXN+10];struct data{
   int v,next,c;}e[MAXN*MAXN*10];bool b[MAXN][MAXN];void add(int u,int v,int c){    e[++cut].v=v;    e[cut].c=c;    e[cut].next=head[u];    head[u]=cut;}inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();    return x*f;}bool bfs(){    memset(dis,-1,sizeof dis);    queue
        
         q;    q.push(0);    dis[0]=0;    while(!q.empty())    {        int u=q.front();q.pop();        for(int i=head[u];i;i=e[i].next)        {            int v=e[i].v;            if(dis[v]==-1&&e[i].c)            {                dis[v]=dis[u]+1;                q.push(v);             }        }    }    return dis[n*n+1]!=-1;}int dfs(int u,int y){    if(u==n*n+1) return y;    int rest=0;    for(int i=head[u];i&&rest
         
          =2&&j>=3&&!b[i-1][j-2]) add((i-1)*n+j,(i-2)*n+j-2,1),add((i-2)*n+j-2,(i-1)*n+j,0); if(i>=3&&j>=2&&!b[i-2][j-1]) add((i-1)*n+j,(i-3)*n+j-1,1),add((i-3)*n+j-1,(i-1)*n+j,0); if(i>=3&&j+1<=n&&!b[i-2][j+1]) add((i-1)*n+j,(i-3)*n+j+1,1),add((i-3)*n+j+1,(i-1)*n+j,0); if(i>=2&&j+2<=n&&!b[i-1][j+2]) add((i-1)*n+j,(i-2)*n+j+2,1),add((i-2)*n+j+2,(i-1)*n+j,0); if(i+2<=n&&j>=2&&!b[i+2][j-1]) add((i-1)*n+j,(i+1)*n+j-1,1),add((i+1)*n+j-1,(i-1)*n+j,0); if(i+1<=n&&j>=3&&!b[i+1][j-2]) add((i-1)*n+j,i*n+j-2,1),add(i*n+j-2,(i-1)*n+j,0); }}int main(){ freopen("knight.in","r",stdin); freopen("knight.out","w",stdout); int x,y; n=read(),m=read(); for(int i=1;i<=m;i++) x=read(),y=read(),b[x][y]=true; slove(); dinic(0,n*n+1); return 0;}