这个题刚看上去就让人不禁想到一道叫做方格取数问题的题目，事实上也就是这么做，对棋盘黑白染色，然后黑格子连源点，白的连汇点，点权为1。然后判断一下黑格子能影响到的白格子，边权为inf，跑一遍最大流就可以了。
笔者惨痛的实践证明，虽然这些题的，额。。DINIC都一模一样，但是不要复制粘贴。。。粘过来一个没优化的可能让你多找半个多小时的错。。。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #define ll long long #define inf 50000000 #define re register #define id n*(i-1)+j using namespace std; struct po { int from,to,dis,nxt; }edge[500001]; int head[500001],cur[500001],dep[50002],n,m,s,t,u,num=-1,x,y,l,tot,sum,d; int nm,a[210][210]; int dx[9]={0,-1,1,2,2,1,-1,-2,-2}; int dy[9]={0,2,2,1,-1,-2,-2,-1,1}; inline int read() { int x=0,c=1; char ch=' '; while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); while(ch=='-')c*=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar(); return x*c; } inline void add_edge(int from,int to,int dis) { edge[++num].nxt=head[from]; edge[num].from=from; edge[num].to=to; edge[num].dis=dis; head[from]=num; } inline void add(int from,int to,int dis) { add_edge(from,to,dis); add_edge(to,from,0); } inline bool bfs() { memset(dep,0,sizeof(dep)); queue<int> q; while(!q.empty()) q.pop(); dep[s]=1; q.push(s); while(!q.empty()) { int now=q.front(); q.pop(); for(re int i=head[now];i!=-1;i=edge[i].nxt) { int v=edge[i].to; if(dep[v]==0&&edge[i].dis>0) { dep[v]=dep[now]+1; if(v==t) return 1; q.push(v); } } } return 0; } inline int dfs(int u,int dis) { if(u==t) return dis; int diss=0; for(re int& i=cur[u];i!=-1;i=edge[i].nxt) { int v=edge[i].to; if(dep[v]==dep[u]+1&&edge[i].dis!=0) { int check=dfs(v,min(dis,edge[i].dis)); if(check>0) { diss+=check; dis-=check; edge[i].dis-=check; edge[i^1].dis+=check; if(dis==0) break; } } } return diss; } inline int dinic() { int ans=0; while(bfs()) { for(re int i=0;i<=t;i++) cur[i]=head[i]; while(int d=dfs(s,inf)) ans+=d; } return ans; } int main() { memset(head,-1,sizeof(head)); n=read();m=read(); sum=n*n; for(re int i=1;i<=n;i++) for(re int j=1;j<=n;j++) a[i][j]=1; for(re int i=1;i<=m;i++) { x=read();y=read(); a[x][y]=2; sum--; } s=0;t=n*n+1; for(re int i=1;i<=n;i++) for(re int j=1;j<=n;j++) { if(a[i][j]!=2) { if((i+j)%2==1) { add(s,id,1); for(re int h=1;h<=8;h++) { int lx=i+dx[h]; int ly=j+dy[h]; if(lx>=1&&lx<=n&&ly>=1&&ly<=n) add(id,(lx-1)*n+ly,inf); } } else add(id,t,1); } } cout<<sum-dinic(); }