题目

https://www.luogu.org/problemnew/show/P3355#sub

---

解题思路

这道题自从上一次得了90分后，就一直搁置了很久，找不到错误。请各位大佬帮忙！！！

---

代码匈牙利算法

#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int b[8]={-2,-1,1,2,2,1,-1,-2},c[8]={1,2,2,1,-1,-2,-2,-1};
struct node{int y,next;}a[320032]; 
int rr,ans,sum,add,n,m,xx,yy,link[40001],v[40001],list[40001],t[201][201];
inline int read()
{int f=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) f=(f<<3)+(f<<1)+c-48,c=getchar();return f;
}
void write(int x){if (x>9) write(x/10); putchar(x%10+48);}
inline bool find (int q){for (register int i=list[q];i;i=a[i].next)if (!v[a[i].y]){v[a[i].y]=1; int u=link[a[i].y]; link[a[i].y]=q; if (!u||find(u)) return 1; link[a[i].y]=u; }	return 0;
}
signed main()
{n=read(); m=read();  ans=n*n-m; for (register int i=1;i<=m;i++) t[(xx=read())][(yy=read())]=-1; for (register int i=1;i<=n;i++)for (register int j=1;j<=n;j++)if (!t[i][j]&&((i+j)&1)){t[i][j]=++add;for (register int k=0;k<8;k++){xx=i+b[k]; yy=j+c[k];if ((xx>=1&&xx<=n)&&(yy>=1&&yy<=n)){if (!t[xx][yy]) t[xx][yy]=++rr; if (t[xx][yy]!=-1) a[++sum].y=t[xx][yy],a[sum].next=list[add],list[add]=sum; }}}for (register int i=1;i<=add;i++){memset(v,0,sizeof(v));if (find(i)) ans--; }write(ans); return 0; 
}