首页 > 代码库 > bzoj 4930: 棋盘
bzoj 4930: 棋盘
Description
给定一个n×n的棋盘，棋盘上每个位置要么为空要么为障碍。定义棋盘上两个位置(x,y),(u,v)能互相攻击当前仅
当满足以下两个条件：
1:x=u或y=v
2:对于(x,y)与(u,v)之间的所有位置，均不是障碍。
现在有q个询问，每个询问给定ki，要求从棋盘中选出ki个空位置来放棋子，问最少互相能攻击到的棋子对数是多少？
Input
第一行一个整数n。
接下来输入一个n×n的字符矩阵，一个位置若为.，则表示这是一个空位置，若为#，则为障碍。
第n+2行输入一个整数q代表询问个数。
接下来q行，每行一个整数k，代表要放的棋子个数。
n ≤ 50, q ≤ 10000, k ≤ 棋盘中空位置数量
Output
输出共q行，每行代表对应询问的最少的互相能攻击到的棋子对数。
不难得出费用流的模型，由于图的特殊性可用bfs求最小费用增广路
#include<cstdio>#include<algorithm>#include<queue>const int inf=0x3f3f3f3f;int n,q,id[55][55][2],id1=0,id2=0,as[2507],ap=0,d[5007],l[5007];char s[55][55];int es[5007],enx[5007],ev[5007],e0[5007],ep=2,lt;void ae(int a,int b){ es[ep]=b;enx[ep]=e0[a];ev[ep]=1;e0[a]=ep++; es[ep]=a;enx[ep]=e0[b];ev[ep]=0;e0[b]=ep++;}bool cmp(int a,int b){ return d[a]<d[b];}int q0[5007],ed[5007],tk=1;std::queue<int>q1;void mins(int&a,int b){if(a>b)a=b;}void cal(int w){ if(w>id1)mins(lt,l[w]+d[w]); for(int i=e0[w];i;i=enx[i])if(ev[i]){ int u=es[i]; if(l[u]>l[w])l[u]=l[w],q1.push(u); }}int dfs(int w){ if(ed[w]==tk)return 0; ed[w]=tk; if(w>id1&&l[w]+d[w]==lt){ ++d[w]; return 1; } for(int i=e0[w];i;i=enx[i])if(ev[i]&&l[es[i]]==l[w]&&dfs(es[i])){ ev[i]=0,ev[i^1]=1; return 1; } return 0;}bool cal(){ lt=inf; for(int i=1;i<=id1;++i)q0[i]=i,l[i]=d[i]; for(int i=id1+1;i<=id2;++i)l[i]=inf; std::sort(q0+1,q0+id1+1,cmp); int qp=1; while(1){ if(qp<=id1){ int w=q0[qp]; if(l[w]!=d[w]){++qp;continue;} if(q1.size()&&l[q1.front()]<l[w])cal(q1.front()),q1.pop(); else cal(w),++qp; }else if(q1.size())cal(q1.front()),q1.pop(); else break; } int flow=0; for(int i=1;i<=id1;++tk,++i)if(l[i]==d[i]&&dfs(i))++flow,++d[i]; for(int i=1;i<=flow;++i)++ap,as[ap]=as[ap-1]+lt; return flow;}int main(){ scanf("%d",&n); for(int i=1;i<=n;++i)scanf("%s",s[i]+1); for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ if(s[i][j]!=‘.‘)continue; id[i][j][0]=s[i-1][j]==‘.‘?id[i-1][j][0]:++id1; id[i][j][1]=s[i][j-1]==‘.‘?id[i][j-1][1]:++id2; } } for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j)if(s[i][j]==‘.‘){ ae(id[i][j][0],id1+id[i][j][1]); } } id2+=id1; while(cal()); for(scanf("%d",&q);q;--q){ int x; scanf("%d",&x); printf("%d\n",as[x]); } return 0;}
bzoj 4930: 棋盘
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。