WA 64pts 求助

rt

#include<bits/stdc++.h>
#define N 40005
#define M 40005
using namespace std;
int sum,n,m,s,t,a[205][205];
int tot=2,head[N];
struct edge{
    int to,next,w;
}e[M*20];
void add(int u,int v,int w)
{
    e[tot]=(edge){v,head[u],w};
    head[u]=tot++;
}
int pre[N],dis[N];
int q[N],l,r;
bool bfs()
{
    l=r=0;
    fill(dis,dis+1+t+1,-1);
    q[++r]=s;
    dis[s]=0;
    pre[s]=head[s];
    while(l<r)
    {
        int now=q[++l];
        for(int i=head[now];i;i=e[i].next)
        {
            int to=e[i].to;
            if(e[i].w&&dis[to]==-1)
            {
                dis[to]=dis[now]+1;
                q[++r]=to;
                pre[to]=head[to];
                if(to==t) return 1;
            } 
        }
    }
    return 0;
}
int dfs(int x,int sum)
{
    if(x==t) return sum;
    int k,cnt=0;
    for(int i=pre[x];i&&sum;i=e[i].next)
    {
        pre[x]=i;
        int v=e[i].to;
        if(e[i].w&&dis[v]==dis[x]+1)
        {
            k=dfs(v,min(sum,e[i].w));
            if(k==0) dis[v]=1e9;
            e[i].w-=k;
            e[i^1].w+=k;
            sum-=k;
            cnt+=k;
        }
    }
    return cnt;
}
int Dinic()
{
    int ans=0;
    while(bfs()) ans+=dfs(s,1e9);
    return ans;
}
int id(int x,int y)
{
    return x*(n-1)+y;
}
int dx[]={1,1,-1,-1,2,2,-2,-2},dy[]={2,-2,2,-2,1,-1,1,-1};
int main()
{
    freopen("a.in","r",stdin);
    scanf("%d%d",&n,&m);
    s=0,t=n*n+1;
    sum=n*n;
    while(m--)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        if(!a[u][v])sum--;
        a[u][v]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]) continue;
            if((i+j)&1) add(s,id(i,j),1),add(id(i,j),s,0);
            else add(id(i,j),t,1),add(t,id(i,j),0);
        }   
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(((i+j)&1)==0||a[i][j]) continue;
            for(int k=0;k<8;k++)
            {
                int x=i+dx[k],y=j+dy[k];
                if(x<1||y<1||x>n||y>n||a[x][y]) continue;
                add(id(i,j),id(x,y),1),add(id(x,y),id(i,j),0);
            }
        }       
    printf("%d",sum-Dinic());
    return 0; 
}
/*
3 2
1 2
3 1
*/