悬赏5馆

36分。

有WA的，有RE的，有TLE的。

感激不尽求求了。看看吧马风好看清奇。

#include <bits/stdc++.h>
#define N 205
#define int long long
const long long inf=2005020600;
using namespace std;
int n,s,t;
int head[100005];
struct grap{
    int to,nxt,w;
} e[100005];
int cnt; 
int dep[100005];
int now[100005]; //最优弧优化
int has(int x,int y){
	return (x-1)*(n)+y;
}
void add(int u,int v,int w){
    cnt++;
    e[cnt].to=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u]; 
    head[u]=cnt; 

    cnt++;
    e[cnt].to=u;
    e[cnt].w=0;
    e[cnt].nxt=head[v];
    head[v]=cnt;
    return ;
}
int bfs(){
    for(int i=0;i<=n*n+1;++i){
        dep[i]=1e18;
    }
    queue<int> q;
    q.push(s);
    dep[s]=0;
    now[s]=head[s]; 
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=e[i].nxt){
            int v=e[i].to;
            if(e[i].w>0 && dep[v]==1e18){
                q.push(v);
                now[v]=head[v];
                dep[v]=dep[x]+1;
                if(v==t) return 1;
            }
        }
    }
    return 0;
}
int dinic(int x,int num){
    if(x==t) return num;
    int k,res=0;
    for(int i=now[x];i&&num;i=e[i].nxt){
        now[x]=i;
        int v=e[i].to;
        if(e[i].w>0 && (dep[v]==dep[x]+1)){
            k=dinic(v,min(num,e[i].w));
            if(k == 0) dep[v]=1e18;
            e[i].w-=k;
            e[i^1].w+=k;
            res+=k;
            num-=k;
        }
    }
    return res;
}

int sum;
int m;
char ch[N][N]; 
int movx[10]={0,-1,-2,1,2,-1,-2,1,2};
int movy[10]={0,-2,-1,-2,-1,2,1,2,1};
int viser[N][N]; 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
	cin>>n>>m;
    s=0;
    t=n*n+1;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            ch[i][j]='0';
        }
    }
    for(int i=1;i<=m;++i){
        int x,y;cin>>x>>y;
        ch[x][y]='1';
    }
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			if(ch[i][j] == '0') sum++; 
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			if((i+j)%2 == 0 && ch[i][j] == '0'){
				for(int k=1;k<=8;++k){
					int sx=i+movx[k];
					int sy=j+movy[k];
					if(sx<1 || sx>n || sy<1 || sy>n){
						continue;
					} 
					if (ch[sx][sy] == '1') continue;
                    add(has(i,j),has(sx,sy),1);
                    // add(has(sx,sy),t,1);
                    // cerr<<has(i,j) << " " << has(sx,sy) << "\n";
				}
                add(s,has(i,j),1);
			}else if(ch[i][j]=='0'){
                add(has(i,j),t,1);
                // cerr<<has(i,j)<<" "<<t<<"\n";
            }
		}
	}
    int ans=0;
	while(bfs()) {
		ans+=dinic(s,1e18);
	}
	cout<<sum-ans<<'\n'; 
}