peterwuyihong @ 2021-04-03 11:59:13
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 250*250
#define maxm 250*250*16
using namespace std;
int n,k,x,y,tot=1,ans;bool Map[250][250];
int head[maxn],Next[maxm],ver[maxm];
short dx[8]={1,1,2,2,-1,-1,-2,-2};
short dy[8]={2,-2,1,-1,2,-2,1,-1};
int query[maxn],cnt;
bool v[maxn];int match[maxn];
void add(int x,int y)
{
ver[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
}
bool dfs(int x)
{
for(int i=head[x],y;i;i=Next[i])
if(!v[y=ver[i]])
{
v[y]=1;
if(match[y]==0||dfs(match[y]))
{
match[y]=x;
return 1;
}
}
return 0;
}
int main()
{
scanf("%d %d",&n,&k);
for(int i=1;i<=k;i++)
{
scanf("%d %d",&x,&y);
Map[x][y]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(!Map[i][j])
{
query[++cnt]=i*250+j;
for(int Case=0;Case<4;Case++)
{
int tx=i+dx[Case],ty=j+dy[Case];
if(Map[tx][ty])continue;
if(tx<1||ty<1||tx>n||ty>n)continue;
// printf("Link (%d,%d) and (%d,%d)\n",i,j,tx,ty);
add(tx*250+ty,i*250+j);
add(i*250+j,tx*250+ty);
}
}
for(int i=1;i<=cnt;i++)
memset(v,0,sizeof v),ans+=dfs(query[i]);
printf("%d\n",n*n-k-(ans>>1));
}
by —只书虫仔 @ 2021-04-03 12:06:19
??!
by Remake_ @ 2021-04-03 12:14:53
这为啥不能对啊
by peterwuyihong @ 2021-04-04 17:36:30
@Miracle_Creator 这咋对啊
by peterwuyihong @ 2021-04-04 17:52:39
明白了,此贴结