记录编号	588111	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 骑士共存	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.570 s
提交时间	2024-05-25 17:11:28	内存使用	7.02 MiB

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
#define F(i,a,b) for(int i = a;i <= b;i++)
#define D(i,a,b) for(int i = a;i >= b;i--)
const int N = 2e5,M = 5e5+10;
const ll inf = 1e17;

ll read(){
    ll x = 0,f = 1;char c = getchar();
    for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
    for(;c >= '0' && c <= '9';c = getchar())x = (x<<3) + (x<<1) + c-'0';
    return x * f;
}

int n,m,s,t;
struct made{
    int ver,nx;ll ed;
};
struct flow{
    made e[M<<1];
    int hd[N],tot = 1;
    void add(int x,int y,ll z){
        e[++tot] = {y,hd[x],z},hd[x] = tot;
        e[++tot] = {x,hd[y],0},hd[y] = tot;
    }
    int d[N],cur[N];
    ll dinic(int x,ll fl){
        if(x == t)return fl;
        ll rest = fl;
        for(int i = cur[x];i && rest;i = e[i].nx){
            int y = e[i].ver;cur[x] = i;// 
            if(e[i].ed && d[y] == d[x] + 1){
                ll c = dinic(y,min(rest,e[i].ed));
                if(!c)d[y] = 0;
                e[i].ed -= c,e[i^1].ed += c;
                rest -= c;
            }
        }
        return fl - rest;
    }
    ll bfs(){
        ll ans = 0;
        while(1){
            memset(d,0,sizeof d);
            memcpy(cur,hd,sizeof hd);
            queue<int>q;
            q.push(s);q.push(s),d[s] = 1;
            while(!q.empty()){
                int x = q.front();q.pop();
                for(int i = hd[x];i;i = e[i].nx){
                    int y = e[i].ver;
                    if(e[i].ed && !d[y])d[y] = d[x] + 1,q.push(y);
                }
            }//分层图 
            if(!d[t])return ans;
            ans += dinic(s,inf);//多路增广 
        }
    }
}f;

int id(int x,int y){return (x-1)*n+y;}
int lx[10] = {0,-2,-1,1,2,2,1,-1,-2},ly[10] = {0,1,2,2,1,-1,-2,-2,-1};
bool v[210][210];
int main(){
    freopen("knight.in","r",stdin);
    freopen("knight.out","w",stdout);
    n = read(),m = read();
    s = n*n+1,t = n*n+2;
    F(i,1,m){
        int x = read(),y = read();
        v[x][y] = 1;
    }
    F(i,1,n){
        F(j,1,n){
            if(v[i][j])continue;
            if((i+j) % 2){
                f.add(s,id(i,j),1);
                F(k,1,8){
                    int x = i+lx[k],y = j+ly[k];
                    if(x < 1 || x > n || y < 1 || y > n)continue;
                    if(!v[x][y])f.add(id(i,j),id(x,y),inf);
                }
            }
            else f.add(id(i,j),t,1);
        }
    }
    printf("%lld\n",1ll * n * n - f.bfs() - m);


    return cerr<<endl<<"Time:"<<clock()<<"ms"<<endl,0;
     
}