题目描述
在一个 n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入
对于给定的 n*n 个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它们彼此互不攻击
输入输出格式
输入格式：
第一行有 2 个正整数n 和 m (1<=n<=200, 0<=m<n2)，分别表示棋盘的大小和障碍数。接下来的 m 行给出障碍的位置。每行 2 个正整数，表示障碍的方格坐标。
输出格式：
将计算出的共存骑士数输出
输入输出样例
输入样例#1：
3 2 1 1 3 3
输出样例#1：
5
解题思路
给棋盘染色，说白了就是给棋盘上的每个格子分个类，像上图棋盘上的格子被分成了黄红两类(国际象棋的棋盘本来就被染成了黑白相间的)，可以发现骑士所在的位置和他能攻击到的位置异色，于是就变成了二分图最大独立集问题了。这篇博文总结的挺好的。
从S向每个白色格子连一条边权为1的边，从每个白色格子向其能攻击到的所有格子连一条边权为inf的边，从所有黑色格子向T连一条边权为1的边，然后跑最小割，又因为最大流等于最小割，所以跑最大流。答案就是所有没障碍的格子数量减去最大流。
源代码
#include<queue> #include<cstdio> #include<cstring> int n,m; int g[210][210]={0}; int s,t; struct Edge{ int next,to,f; }e[1000010]={0}; int cnt=2,head[1000010]={0}; void add(int u,int v,int f) { e[cnt]={head[u],v,f}; head[u]=cnt++; e[cnt]={head[v],u,0}; head[v]=cnt++; } int dis[1000010]={0}; bool bfs() { memset(dis,0,sizeof(dis)); dis[s]=1; std::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,std::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 dinic() { int ans=0; while(bfs()) { while(int temp=dfs(s,0x7fffffff)) ans+=temp; } return ans; } inline int id(int x,int y) { return (x-1)*n+y; } int main() { //freopen("knight.in","r",stdin); //freopen("knight.out","w",stdout); scanf("%d%d",&n,&m); s=n*n+1,t=s+1; int ans=n*n-m; for(int i=1,x,y;i<=m;i++) { scanf("%d%d",&x,&y); g[x][y]=-1;//不可到 } int bh[8][2]={{1,2},{2,1},{-2,1},{-1,2},{1,-2},{2,-1},{-1,-2},{-2,-1}}; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(g[i][j]==-1) continue; if((i+j)&1) { add(s,id(i,j),1); for(int k=0;k<8;k++) { int ii=i+bh[k][0],jj=j+bh[k][1]; if(ii>0&&ii<=n&&jj>0&&jj<=n&&g[ii][jj]==0) add(id(i,j),id(ii,jj),0x7fffffff); } } else { add(id(i,j),t,1); } } } printf("%d\n",ans-dinic()); return 0; }
