首页 > 代码库 > AC日记——[网络流24题]骑士共存 cogs 746
AC日记——[网络流24题]骑士共存 cogs 746
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
- 思路：
- 染色；
- s到黄色连边，流量1；
- 红色到t连边，流量1；
- 然后黄色周围8个点能跳到的点连边，流量INF；
- 上述所有的点都剔除障碍；
- 来，上代码：
#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;struct EdgeType { int v,e,f;};struct EdgeType edge[50050*50];const int dx[9]={0,-2,-1,1,2,2,1,-1,-2};const int dy[9]={0,1,2,2,1,-1,-2,-2,-1};int n,m,s=0,t,head[50050],cnt=1,ans,deep[50050];char Cget;bool if_[205][205];inline void in(int &now){ now=0,Cget=getchar(); while(Cget>‘9‘||Cget<‘0‘) Cget=getchar(); while(Cget>=‘0‘&&Cget<=‘9‘) { now=now*10+Cget-‘0‘; Cget=getchar(); }}inline void edge_add(int u,int v,int w){ edge[++cnt].v=v,edge[cnt].f=w,edge[cnt].e=head[u],head[u]=cnt; edge[++cnt].v=u,edge[cnt].f=0,edge[cnt].e=head[v],head[v]=cnt;}bool BFS(){ queue<int>que; for(int i=s;i<=t;i++) deep[i]=-1; deep[s]=0,que.push(s); while(!que.empty()) { int now=que.front();que.pop(); for(int i=head[now];i;i=edge[i].e) { if(deep[edge[i].v]<0&&edge[i].f) { deep[edge[i].v]=deep[now]+1; if(edge[i].v==t) return true; que.push(edge[i].v); } } } return false;}int flowing(int now,int flow){ if(now==t||flow<=0) return flow; int oldflow=0; for(int i=head[now];i;i=edge[i].e) { if(edge[i].f<=0||deep[edge[i].v]!=deep[now]+1) continue; int pos=flowing(edge[i].v,min(flow,edge[i].f)); flow-=pos; oldflow+=pos; edge[i].f-=pos; edge[i^1].f+=pos; if(flow==0) return oldflow; } if(oldflow==0) deep[now]=-1; return oldflow;}int main(){ freopen("knight.in","r",stdin); freopen("knight.out","w",stdout); in(n),in(m); ans=n*n-m; t=n*n+1;int x,y; while(m--) { in(x),in(y); if_[x][y]=true; } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(if_[i][j]) continue; if((i+j)%2==0) { edge_add(s,(i-1)*n+j,1); for(int v=1;v<=8;v++) { if(i+dx[v]>0&&i+dx[v]<=n&&j+dy[v]>0&&j+dy[v]<=n) { if(!if_[i+dx[v]][j+dy[v]]) { edge_add((i-1)*n+j,(i+dx[v]-1)*n+j+dy[v],0x7ffffff); } } } } else edge_add((i-1)*n+j,t,1); } } while(BFS()) ans-=flowing(s,0x7ffffff); cout<<ans; return 0;}
AC日记——[网络流24题]骑士共存 cogs 746
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。