首页 > 代码库 > 洛谷 P3355 骑士共存问题
洛谷 P3355 骑士共存问题
题目描述
在一个 n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入
对于给定的 n*n 个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它们彼此互不攻击
输入输出格式
输入格式：
第一行有 2 个正整数n 和 m (1<=n<=200, 0<=m<n2)，分别表示棋盘的大小和障碍数。接下来的 m 行给出障碍的位置。每行 2 个正整数，表示障碍的方格坐标。
输出格式：
将计算出的共存骑士数输出
输入输出样例
输入样例#1：
3 21 13 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;}
洛谷 P3355 骑士共存问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。