题意：给你一个棋盘，然后有一个骑士rider，棋盘上有一些障碍，问你最多放多少个骑士
思路：期初我一直以为这种题是什么八皇后问题的变形，队友告诉我，这是网络流，由于这道题的黄色格子上的棋子的下一步总是调到红色格子上，所以我们把所有的红色格子连到一个超级源上，所有的黄色格子连接到一个超级汇上，然后对于每个可以跳到的位置我们在建立一条边，容量为1 ，因为我们最后求的是这张图的最小割，而最小割定理我们知道，最小割其实就是图的最大流，之前的 板子可能出了一点点问题，不在用了，总是TLE，不知道为什么，很玄学（玄不救非，氪不改命！！）
代码:
#include <set> #include <map> #include <queue> #include <stack> #include <math.h> #include <vector> #include <string> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <algorithm> #define zero(a) fabs(a)<eps #define lowbit(x) (x&(-x)) #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define MOD 1000000007 int max(int x,int y){return x>y?x:y;}; int min(int x,int y){return x<y?x:y;}; int max(int x,int y,int z){return max(x,max(y,z));}; int min(int x,int y,int z){return min(x,min(y,z));}; typedef long long LL; const double PI=acos(-1.0); const double eps=1e-8; const int inf=0x3f3f3f3f; const int INF=0x7fffffff; const LL linf=0x3f3f3f3f3f3f3f3fLL; int dir[8][2]= {1,2,-1,2,2,1,-2,1,-1,-2,1,-2,-2,-1,2,-1}; using namespace std; int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } using namespace std; struct Edge{ int next,to,f; }; struct Dinic { int s,t; Edge e[1000010]; int cnt=2,head[1000010]={0}; int dis[1000010]={0}; Dinic (){} void init(int _s,int _t) { s=_s,t=_t; } void addedge(int u,int v,int f) { e[cnt]={head[u],v,f}; head[u]=cnt++; e[cnt]={head[v],u,0}; head[v]=cnt++; } bool bfs() { memset(dis,0,sizeof(dis)); dis[s]=1; queue<int> q; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(!dis[v]&&e[i].f>0) { dis[v]=dis[u]+1; q.push(v); } } } return dis[t]!=0; } int dfs(int u,int flow) { if(u==t||flow==0) return flow; int flow_sum=0; for(int i=head[u];i;i=e[i].next) { int v=e[i].to,f=e[i].f; if(dis[v]!=dis[u]+1||f==0) continue; int temp=dfs(v,min(flow-flow_sum,f)); e[i].f-=temp; e[i^1].f+=temp; flow_sum+=temp; if(flow_sum>=flow) break; } if(!flow_sum) dis[u]=-1; return flow_sum; } int maxflow() { int ans=0; while(bfs()) { while(int temp=dfs(s,INF)) ans+=temp; } return ans; } }DC; #define id(x,y) ((x-1)*n+y) bool mp[210][210]; int main() { int n,m; n=read(),m=read(); int t=n*n+1; int s=0; DC.init(s,t); for(int i=1;i<=m;i++){ int p,q; p=read(),q=read(); mp[p][q]=1; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(mp[i][j])continue; if((i+j)%2){ DC.addedge(DC.s,id(i,j),1); for(int k=0;k<8;k++){ int p=i+dir[k][0]; int q=j+dir[k][1]; if(p<1||p>n||q<1||q>n||mp[p][q]) continue; DC.addedge(id(i,j),id(p,q),inf); } } else{ DC.addedge(id(i,j),DC.t,1); } } } int ans=DC.maxflow(); printf("%d ",n*n-m-ans); return 0; }