首页 > 代码库 > [COGS746] [网络流24题] 骑士共存
[COGS746] [网络流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)
分别表示棋盘的大小和障碍数。接下来的m 行给出障碍的位置。每行2 个正整数，表示障
碍的方格坐标。
«结果输出:
将计算出的共存骑士数输出到文件knight.out。
输入文件示例 输出文件示例
knight.in
3 2
1 1
3 3
knight.out
思路
网络流
http://www.cnblogs.com/shenben/p/6259661.html
代码实现
1 #include<cstdio> 2 #include<cstring> 3 const int maxn=800; 4 const int maxs=maxn*maxn; 5 inline int min_(int x,int y){return x<y?x:y;} 6 int n,m,s,t,ans; 7 int a,b,nh,nl; 8 int map[maxn][maxn]; 9 int hb[]={-2,-1,1,2,2,1,-1,-2};10 int lb[]={1,2,2,1,-1,-2,-2,-1};11 int h[maxs],hs=1,ew[maxs],et[maxs],en[maxs];12 void add(int u,int v){13 ++hs,ew[hs]=1,et[hs]=v,en[hs]=h[u],h[u]=hs;14 ++hs,ew[hs]=0,et[hs]=u,en[hs]=h[v],h[v]=hs;15 }16 int q[maxs],head,tail;17 int d[maxs];18 void bfs(){19 memset(d,0,sizeof(d));20 head=tail=0;21 q[head++]=s,d[s]=1;22 while(head>tail){23 a=q[tail++];24 for(int i=h[a];i;i=en[i])25 if(!d[et[i]]&&ew[i]){26 d[et[i]]=d[a]+1;27 if(et[i]==t) return;28 q[head++]=et[i];29 }30 }31 }32 int ap(int k,int w){33 if(k==t) return w;34 int dw=w;35 for(int i=h[k];i&&dw;i=en[i])36 if(ew[i]&&d[et[i]]==d[k]+1){37 int wt=ap(et[i],min_(w,ew[i]));38 if(wt) ew[i]-=wt,ew[i^1]+=wt,dw-=wt;39 else d[et[i]]=0;40 }41 return w-dw;42 }43 void Dinic(){while(bfs(),d[t]) ans-=ap(s,ans);}44 int main(){45 freopen("knight.in","r",stdin);46 freopen("knight.out","w",stdout);47 scanf("%d%d",&n,&m);48 s=0,t=1,ans=n*n-m;49 for(int i=1;i<=n;i++)50 for(int j=1;j<=n;j++)51 map[i][j]=i&1^j&1;52 for(int i=1;i<=m;i++){53 scanf("%d%d",&a,&b);54 map[a][b]=2;55 }56 for(int i=1;i<=n;i++)57 for(int j=1;j<=n;j++)58 if(!map[i][j]){59 add(s,i*n+j);60 for(int k=0;k<8;k++){61 nh=i+hb[k],nl=j+lb[k];62 if(nh>0&&nh<=n&&nl>0&&nl<=n&&map[nh][nl]==1)63 add(i*n+j,nh*n+nl);64 }65 }66 else if(map[i][j]==1) add(i*n+j,t);67 Dinic();68 printf("%d\n",ans);69 return 0;70 }
[COGS746] [网络流24题] 骑士共存
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。