记录编号	195804	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 骑士共存	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	0.891 s
提交时间	2015-10-19 21:06:05	内存使用	6.68 MiB

#include<cstdio>
#include<cstring>

using namespace std;

int n,m;
int x,y,ans,z;
bool v[40010];
int sum,tot,first[40010];
int a[210][210],match[40010],zbd[40010];

struct Edge{
    int qd,zd,next;
}edge[500000];

void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        a[x][y]=-1;
    }
}

void add(int qd,int zd)
{
     edge[++tot].qd=qd;
     edge[tot].zd=zd;
     edge[tot].next=first[qd];
     first[qd]=tot;
}

void makegrafh()
{
     for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++)
             if(a[i][j]==0)
                 a[i][j]=++sum;
     for(int i=1;i<=n;i++){
         for(int j=0;j<i;j++){
            int x=i-j,y=i+j;
            if(x>0&&y<=n&&a[x][y]>0){
                zbd[++z]=a[x][y];
                if(x+2<=n){
                     if(y+1<=n&&a[x+2][y+1]>0)
                         add(a[x][y],a[x+2][y+1]);
                     if(y-1>0&&a[x+2][y-1]>0)
                         add(a[x][y],a[x+2][y-1]);
                }
                if(x-2>0){
                    if(y+1<=n&&a[x-2][y+1]>0)
                        add(a[x][y],a[x-2][y+1]);
                    if(y-1>0&&a[x-2][y-1]>0)
                       add(a[x][y],a[x-2][y-1]);
                }
                if(x-1>0){
                    if(y-2>0&&a[x-1][y-2]>0)
                        add(a[x][y],a[x-1][y-2]);
                    if(y+2<=n&&a[x-1][y+2]>0)
                        add(a[x][y],a[x-1][y+2]);
                }
                if(x+1<=n){
                    if(y-2>0&&a[x+1][y-2]>0)
                        add(a[x][y],a[x+1][y-2]);
                    if(y+2<=n&&a[x+1][y+2]>0)
                        add(a[x][y],a[x+1][y+2]);
                }
            }
            if(j!=0){
                x=i+j;y=i-j;
                if(x<=n&&y>0&&a[x][y]>0){
                    zbd[++z]=a[x][y];
                    if(x+2<=n){
                         if(y+1<=n&&a[x+2][y+1]>0)
                             add(a[x][y],a[x+2][y+1]);
                         if(y-1>0&&a[x+2][y-1]>0)
                             add(a[x][y],a[x+2][y-1]);
                    }
                    if(x-2>0){
                        if(y+1<=n&&a[x-2][y+1]>0)
                            add(a[x][y],a[x-2][y+1]);
                        if(y-1>0&&a[x-2][y-1]>0)
                           add(a[x][y],a[x-2][y-1]);
                    }
                    if(x-1>0){
                        if(y-2>0&&a[x-1][y-2]>0)
                            add(a[x][y],a[x-1][y-2]);
                        if(y+2<=n&&a[x-1][y+2]>0)
                            add(a[x][y],a[x-1][y+2]);
                    }
                    if(x+1<=n){
                        if(y-2>0&&a[x+1][y-2]>0)
                            add(a[x][y],a[x+1][y-2]);
                        if(y+2<=n&&a[x+1][y+2]>0)
                            add(a[x][y],a[x+1][y+2]);
                    }
                }
            }
         }
     }
}

bool dfs(int x)
{
     for(int i=first[x];i;i=edge[i].next){
         int zd=edge[i].zd;
         if(!v[zd]){
             v[zd]=1;
             if(!match[zd]||dfs(match[zd])){
                  match[zd]=x;
                  return true;
             }
         }
     }
     return false;
}

int main()
{
    freopen("knight.in","r",stdin);
	freopen("knight.out","w",stdout);
    init();makegrafh();
    for(int i=1;i<=z;i++){
        memset(v,0,sizeof(v));
        if(dfs(zbd[i]))ans++;
    }
    printf("%d",sum-ans);
}