用最大流和匈牙利算法分别写了一下，发现最大流要快一些。正好看没人用最大流就贴在这里吧。

Dinic算法代码

#include<bits/stdc++.h>
using namespace std;
const int N=110;

int n,m,S,T;
int n1,g1[N][N];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int h[10010],ne[80010],e[80010],flow[80010],idx;
int trip[N][N];

void add(int a,int b,int v)
{
    flow[idx]=v,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dist[10010];
int q[10010],hh,tt;
int bfs()
{
    memset(dist,0x3f,sizeof dist);
    dist[S]=0;
    hh=-1,tt=0;
    q[++hh]=S;
    while(hh<=tt)
    {
        int x=q[hh++];
        for(int i=h[x];~i;i=ne[i])
        {
            int j=e[i];
            if(flow[i]&&dist[j]>dist[x]+1)
                dist[j]=dist[x]+1,q[++tt]=j;
        }
    }
    return dist[T];
}

int dfs(int u,int fl)
{
    if(u==T) return fl;
    int res=0;
    for(int i=h[u];~i&&fl;i=ne[i])
    {
        int j=e[i];
        if(flow[i]&&dist[j]==dist[u]+1)
        {
            int x=dfs(j,min(fl,flow[i]));
            fl-=x,res+=x,flow[i]-=x,flow[i^1]+=x;
        }
    }

    if(!res) dist[u]=2e9;
    return res;
}

int maxflow()
{
    int res=0;
    while(bfs()<1e9) res+=dfs(S,INT_MAX);
    return res;
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    while(m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        trip[x][y]=1;
    }
    S=0,T=n*n+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            g1[i][j]=++n1;
            if(i+j&1) add(n1,T,1),add(T,n1,0);
            else add(S,n1,1),add(n1,S,0);
        }    

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if((i+j)%2==0&&!trip[i][j])
                for(int u=0;u<4;u++)
                {
                    int a=i+dx[u],b=j+dy[u];
                    if(a>0&&a<=n&&b>0&&b<=n&&!trip[a][b])
                        add(g1[i][j],g1[a][b],1),add(g1[a][b],g1[i][j],0);
                }
    cout<<maxflow();
    return 0;
}