不知道，我用的Dinic
by PrincessQi @ 2020-03-22 20:15:16
@[一只大头](/user/149192) V改成15000试试
by ♘GoldHookDream♞ @ 2020-03-22 20:25:16
@[eason0511](/user/103835) 亲测RE+WA
by __gcd @ 2020-03-22 20:27:20
@[一只大头](/user/149192) 我的匈牙利，拿着看看吧……
```cpp
#include <bits/stdc++.h>
using namespace std;
const int dx[]={-2,-1,1,2,2,1,-1,-2};
const int dy[]={1,2,2,1,-1,-2,-2,-1};
const int MAX_N=205;
int tot[2],A[MAX_N][MAX_N];
bool ok[MAX_N][MAX_N];
int n,m;
vector<int> g[MAX_N*MAX_N/2];
bool used[MAX_N*MAX_N/2];
int match[MAX_N*MAX_N/2];
bool dfs(int v)
{
used[v]=true;
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i];
if(match[to]==-1 || !used[match[to]] && dfs(match[to]))
{
match[to]=v;
return true;
}
}
return false;
}
int bipartite_matching()
{
memset(match,-1,sizeof(match));
int ret=0;
for(int i=tot[1];i>=1;i--)
{
memset(used,false,sizeof(used));
ret+=dfs(i);
}
return ret;
}
bool in(int x,int y)
{
return x>0 && x<=n && y>0 && y<=n;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
ok[i][j]=true;
}
}
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
ok[x][y]=false;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(!ok[i][j])continue;
A[i][j]=++tot[(i+j)%2];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(A[i][j] && (i+j)%2)
{
for(int k=0;k<8;k++)
{
int x=i+dx[k],y=j+dy[k];
if(in(x,y) && A[x][y])g[A[i][j]].push_back(A[x][y]);
}
}
}
}
cout<<tot[0]+tot[1]-bipartite_matching()<<endl;
return 0;
}
```
by Smile_Cindy @ 2020-03-22 20:48:18
@[Alpha](/user/87058) thx
by __gcd @ 2020-03-22 20:48:39
忘了说，虽然匈牙利的复杂度为 $O(nm)$ 理论上不可通过本题，但是常数小得奇怪的匈牙利还是在一通优化之后通过了本题。
by Smile_Cindy @ 2020-03-22 21:15:28
@[一只大头](/user/149192)
```cpp
#include<bits/stdc++.h>
using namespace std;
const int dx[8]={1,2,2,1,-1,-2,-2,-1};
const int dy[8]={-2,-1,1,2,-2,-1,1,2};
int n,m,match[40010],ans;
bool vis[40010],bj[210][210];
vector<int> nbr[40010];
bool dfs(int x){
for(int i=0;i<nbr[x].size();i++){
int y=nbr[x][i];
if(vis[y]==0){
vis[y]=1;
if(match[y]==0||dfs(match[y])==1){
match[y]=x;
return 1;
}
}
}
return 0;
}
int get(int x,int y){
return (x-1)*n+y;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
bj[x][y]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if((i+j)%2||bj[i][j])
continue;
for(int k=0;k<8;k++){
int nx=i+dx[k],ny=j+dy[k];
if(nx>0&&ny>0&&nx<=n&&ny<=n&&bj[nx][ny]==0)
nbr[get(i,j)].push_back(get(nx,ny));
}
}
for(int i=1;i<=n*n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i))
ans++;
}
cout<<n*n-ans-m;
return 0;
}
```
by 杨氏之子 @ 2020-03-22 22:03:46