记录编号	587318	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 骑士共存	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	0.286 s
提交时间	2024-03-23 16:06:14	内存使用	4.88 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std; 
const int inf=1<<29;
const int maxn=50100,maxm=801000;
int h[maxn],v[maxm],e[maxm],ne[maxm],d[maxn],now[maxn],a[210][210]={},xh[210][210];
int n,n2,m,s,t,tot,maxflow,num=0,ans;
int dis[8][2]={{-1,-2},{-2,-1},{1,-2},{2,-1},{-2,1},{-1,2},{1,2},{2,1}};
struct wz{
    int x;
    int y;
}ys[50010];
void cs()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            num++;
            xh[i][j]=num;
            ys[num].x=i;
            ys[num].y=j;
        }
    }
}
int p(int c,int d)
{
    if(c>0&&c<=n&&d>0&&d<=n)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
void add(int x,int y,int z)
{
    tot++;
    v[tot]=y;
    e[tot]=z;
    ne[tot]=h[x];
    h[x]=tot;
    tot++;
    v[tot]=x;
    e[tot]=0;
    ne[tot]=h[y];
    h[y]=tot;
}
int bfs()
{
    memset(d,0,sizeof(d));
    queue<int> q;
    q.push(s);
    d[s]=1;
    now[s]=h[s];
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=h[x];i;i=ne[i])
        {
            int y=v[i];
            if(e[i]&&d[y]==0)
            {
                q.push(y);
                now[y]=h[y];
                d[y]=d[x]+1;
                if(y==t)
                {
                    return 1;
                }
            }
        }
    }
    return 0;
}
int dinic(int x,int flow)
{
    if(x==t)
    {
        return flow;
    }
    int rest=flow;
    int k;
    for(int i=now[x];i&&rest;i=ne[i])
    {
        now[x]=i;
        int y=v[i];
        if(e[i]&&d[y]==d[x]+1)
        {
            k=dinic(y,min(rest,e[i]));
            if(k==0)
            {
                d[y]=0;
            }
            e[i]-=k;
            e[i^1]+=k;
            rest-=k;
        }
    }
    return flow-rest;
}
int main()
{
    freopen("knight.in","r",stdin);
    freopen("knight.out","w",stdout);
    scanf("%d%d",&n,&m);
    cs();
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=1;
    }
    n2=n*n;
    s=0;
    t=n2+2;
    tot=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]==1)
            {
                continue;
            }
            int yxh=xh[i][j];
            if((i+j)&1==1)
            {
                for(int k=0;k<8;k++)
                {
                    int nx=i+dis[k][0];
                    int ny=j+dis[k][1];
                    if(p(nx,ny)==1&&a[nx][ny]!=1)
                    {
                       int nxh=xh[nx][ny];
                       add(yxh,nxh,inf);
                    }
                }
                add(s,yxh,1);
            }
            else
            {
                add(yxh,t,1);
            }
        }
    }
    int flow=0;
    while(bfs())
    {
        while(flow=dinic(s,inf))
        {
            maxflow+=flow;
        }
    }
    ans=n2-m-maxflow;
    printf("%d",ans);
    return 0;
}