SSL-1344 Knights【最大独立セット】

大意
nで×n n × nの碁盤にはm m点が引かれていますが、今は馬を何頭まで入れることができますかと聞いています.
データ範囲
n<=200,m<=n n <= 200 , m <= n
構想
ハンガリーアルゴリズム我々は定理を知っている:U=V−M U=V−M;V V=頂点数,M=最大整合数(最小オーバーライド数),U=最大独立セット.だから、私たちは各点にラベルをつけますが、1を押すわけではありません.n∗n 1.. n増広路を探す時、n nまでスキャンすることができなくて、8つの方向を列挙することができて、もちろん隣接する表も使うことができて、時間の複雑度は自然に前者より優れて、すべての点がすべて8つの方向に歩くことができるのではありませんため
コード#コード#

#include
#include
#define N 202
#define M 20002
#define LL long long
#define r(i,a,b) for(int i=a;i<=b;i++)
using namespace std;int n,m,ans,one,g[N][N],two,link[M],xq[M][2];
bool vis[M],ok[N][N];
const short dx[8]={1,1,-1,-1,2,2,-2,-2};
const short dy[8]={-2,2,-2,2,-1,1,-1,1};//       
LL read()//      
{
    char c;int f=0,d=1;
    while((c=getchar())<48||c>57)if(c=='-')d=-1;f=(f<<3)+(f<<1)+c-48;
    while((c=getchar())>=48&&c<=57)f=(f<<3)+(f<<1)+c-48;
    return d*f;
}
bool check(int x,int y)
{
    if(x<1||x>n||y<1||y>n) return false;//        
    if(ok[x][y]||vis[g[x][y]]) return false;//             
    return true;//      
}
bool find(int x)//   
{
    int k=0,q=0,x1,y1;
    r(i,0,7)//             2000ms
    {
        x1=xq[x][0]+dx[i];
        y1=xq[x][1]+dy[i];
        if(check(x1,y1))//  
        {
            k=g[x1][y1];
            q=link[k];
            link[k]=x;
            vis[k]=true;
            if(!q||find(q)) return true;
            link[k]=q;
        }
    }
    return false;
}
int main()
{
    n=read();m=read();
    r(i,1,m) ok[read()][read()]=true;
    r(i,1,n)
     r(j,1,n)
      if(!ok[i][j])
       {
        if((i+j)&1)
         g[i][j]=++one;//     
        else
        {
            g[i][j]=++two;//     
            xq[two][0]=i;
            xq[two][1]=j;
        }
       }
    ans=n*n-m;//   
    r(i,1,two)
    {
        memset(vis,0,sizeof(vis));
        if(find(i)) ans--;//     
    }
    printf("%d",ans);//      
}