关于这题用 ISAP 过不去而 dinic 和匈牙利都能过这件事

RT，这样卡是否有些离谱了……

或者说有没有人能给蒟蒻一点卡常的建议？

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int inf=1<<30;
int fx[8][2]={{2,1},{2,-1},{1,2},{1,-2},{-2,1},{-2,-1},{-1,2},{-1,-2}};
int n,m,x,y,s,t,tot=1,bj[201][201],fir[40005],nxt[1000001],to[1000001],cap[1000001],flow[1000001],pre[40005],h[40005],hsl[40005];
queue<int> q;
int ch(int i,int j){return (i-1)*n+j;}
void ins(int x,int y,int v)
{
    nxt[++tot]=fir[x];
    fir[x]=tot;
    to[tot]=y;
    cap[tot]=v;
}
void seth(int t)
{
    memset(h,-1,sizeof(h));
    q.push(t);h[t]=0;
    while(!q.empty())
    {
        int now=q.front();q.pop();
        hsl[h[now]]++;
        for(int i=fir[now];i;i=nxt[i])
            if(h[to[i]]==-1)
            {
                h[to[i]]=h[now]+1;
                q.push(to[i]);
            }
    }
}
int ISAP(int s,int t)
{
    seth(t);
    int now=s,ans=0,d=1<<30;
    while(h[s]<n*n+2)
    {
        if(now==s) d=1<<30;
        int i=fir[now];
        for(;i;i=nxt[i])
            if(cap[i]>flow[i]&&h[now]==h[to[i]]+1)
            {
                d=min(d,cap[i]-flow[i]);
                now=to[i];pre[to[i]]=i;
                if(now==t)
                {
                    while(now!=s)
                    {
                        int k=pre[now];
                        flow[k]+=d;flow[k^1]-=d;
                        now=to[k^1];
                    }
                    ans+=d;d=1<<30;
                }
                break;
            }
        if(!i)
        {
            if(--hsl[h[now]]==0) break;
            int minh=n*n+1;
            for(int j=fir[now];j;j=nxt[j])
                if(cap[j]>flow[j]) minh=min(minh,h[to[j]]);
            h[now]=minh+1;
            hsl[h[now]]++;
            if(now!=s) now=to[pre[now]^1];
        }
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);s=n*n+1,t=s+1;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        bj[x][y]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(bj[i][j]) continue;
            int cur=ch(i,j);
            if((i+j)%2==0)
            {
                ins(s,cur,1),ins(cur,s,0);
                for(int l=0;l<8;l++)
                {
                    int ni=i+fx[l][0],nj=j+fx[l][1],np=ch(ni,nj);
                    if(ni>=1&&nj>=1&&ni<=n&&nj<=n&&!bj[ni][nj])
                        ins(cur,np,inf),ins(np,cur,0);
                }
            }
            else ins(cur,t,1),ins(t,cur,0);
        }
    printf("%d",n*n-m-ISAP(s,t));
    return 0;
}