首页 > 代码库 > [网络流24题] 骑士共存
[网络流24题] 骑士共存
746. [网络流24题] 骑士共存
★★☆ 输入文件：knight.in 输出文件：knight.out 简单对比时间限制：1 s 内存限制：128 MB
- 骑士共存问题
- «问题描述：
- 在一个n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘
上某些方格设置了障碍，骑士不得进入。
- «编程任务：
- 对于给定的n*n个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑
- 士，使得它们彼此互不攻击。
- «数据输入：
- 由文件knight.in给出输入数据。第一行有2 个正整数n 和m (1<=n<=200, 0<=m<=n*n)<n2)，< span="">
- 分别表示棋盘的大小和障碍数。接下来的m 行给出障碍的位置。每行2 个正整数，表示障
- 碍的方格坐标。
- «结果输出:
- 将计算出的共存骑士数输出到文件knight.out。
- 输入文件示例 输出文件示例
- knight.in
- 3 2
- 1 1
3 3
knight.out
- 5
【题解】：
首先把棋盘黑白染色，使相邻格子颜色不同。把所有可用的黑色格子看做二分图X集合中顶点，可用的白色格子看做Y集合顶点。从S向X集合中每个点连接一条容量为1的有向边，从Y集合中每个点向T连接一条容量为1的有向边。从每个可用的黑色格子向骑士一步能攻击到的可用的白色格子连接一条容量为无穷大的有向边。求最小割，结果就是可用格子的数量减去最小割。
【代码】：
#include<cstdio>#include<iostream>using namespace std;const int dx[]={1,1,2,2,-1,-1,-2,-2};const int dy[]={2,-2,1,-1,2,-2,1,-1};const int N=210;const int M=N*N;const int inf=0x3f3f3f3f;int n,m,S,T,num,id[N][N],mp[N][N],head[M],dis[M],q[M*5];struct node{ int v,next,cap;}e[M*10];int tot=1;void add(int x,int y,int z){ e[++tot].v=y;e[tot].cap=z;e[tot].next=head[x];head[x]=tot; e[++tot].v=x;e[tot].cap=0;e[tot].next=head[y];head[y]=tot;}bool bfs(){ for(int i=S;i<=T;i++) dis[i]=inf; int h=0,t=1; q[t]=S;dis[S]=0; while(h!=t){ int x=q[++h]; for(int i=head[x];i;i=e[i].next){ int v=e[i].v; if(e[i].cap&&dis[v]>dis[x]+1){ dis[v]=dis[x]+1; if(v==T) return 1; q[++t]=v; } } } return dis[T]<inf;}int dfs(int x,int f){ if(x==T) return f; int used=0,t; for(int i=head[x];i;i=e[i].next){ int v=e[i].v; if(e[i].cap&&dis[v]==dis[x]+1){ t=dfs(v,min(f,e[i].cap)); //if(!t) dis[t]=0;//TLE*1 e[i].cap-=t;e[i^1].cap+=t; f-=t;used+=t; if(!f) return used; } } dis[x]=0;//TLE*2 return used;}int dinic(){ int res=0; while(bfs()) res+=dfs(S,inf); return n*n-m-res;}void mapping(){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ id[i][j]=++num; } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(mp[i][j]) continue; if((i+j)&1^1){//黑 add(S,id[i][j],1); for(int k=0;k<8;k++){ int nx=i+dx[k],ny=j+dy[k]; if(nx<1||nx>n||ny<1||ny>n||mp[nx][ny]) continue; add(id[i][j],id[nx][ny],1); } } else{//白 add(id[i][j],T,1); } } }}int main(){ freopen("knight.in","r",stdin); freopen("knight.out","w",stdout); scanf("%d%d",&n,&m);S=0;T=n*n+1; for(int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),mp[x][y]=1; mapping(); printf("%d",dinic()); return 0;}
[网络流24题] 骑士共存
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。