题解参考：https://www.cnblogs.com/mrclr/p/9694664.html
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#define maxn 40005
#define maxm 800005
using namespace std;
const int inf=1<<30;
int a[8][2]={{-2,-1},{-2,1},{-1,2},{-1,-2},{2,-1},{2,1},{1,2},{1,-2}};
int mp[205][205];
int num,lst[maxn],cur[maxn],dep[maxn];
int s,t,n,m;
queue<int>q;
struct in
{
int to,nxt,re;
}e[maxm];
void add(int x,int y,int z)
{
e[++num].to=y;e[num].nxt=lst[x];lst[x]=num;e[num].re=z;
e[++num].to=x;e[num].nxt=lst[y];lst[y]=num;e[num].re=0;
}
void clear()
{
num=-1;
memset(lst,-1,sizeof(lst));
}
int bfs()
{
int i,u,v;
while (!q.empty()) q.pop();
memset(dep,-1,sizeof(dep));
dep[s]=0;
q.push(s);
while(!q.empty())
{
u=q.front();
q.pop();
for(i=lst[u];i!=-1;i=e[i].nxt)
{
v=e[i].to;
if (e[i].re && dep[v]==-1)
{
dep[v]=dep[u]+1;
q.push(v);
}
}
}
return dep[t]!=-1;
}
int dfs(int u,int flow)
{
if (u==t || !flow) return flow;
int i,v,res,used=0;
for (i=cur[u];i!=-1;i=e[i].nxt)
{
v=e[i].to;
cur[u]=i;
if (dep[v]==dep[u]+1 && e[i].re)
{
res=dfs(v,min(flow,e[i].re));
if (res)
{
used+=res;
flow-=res;
e[i].re-=res;
e[i^1].re+=res;
if (!flow) return used;
}
}
}
if (flow) dep[u]=-1;
return used;
}
int dinic()
{
int i,maxflow=0;
while (bfs())
{
for (i=0;i<=t;i++) cur[i]=lst[i];
maxflow+=dfs(s,inf);
}
return maxflow;
}
int main()
{
int x,y,i,j,k;
clear();
memset(mp,0,sizeof(mp));
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
mp[x][y]=1;
}
s=0;t=n*n+1;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{
if (mp[i][j]) continue;
//printf("ij %d %d\n",i,j);
if ((i+j)&1)
{
add(s,(i-1)*n+j,1);
for (k=0;k<8;k++)
{
x=i+a[k][0];
y=j+a[k][1];
//printf("xy %d %d %d %d %d\n",x,y,k,a[k][0],a[k][1]);
if (x<1 || y<1 || x>n || y>n || mp[x][y]) continue;
add((i-1)*n+j,(x-1)*n+y,inf);
}
}
else add((i-1)*n+j,t,1);
}
printf("%d\n",n*n-m-dinic());
return 0;
}
View Code