首页 > 代码库 > [BZOJ 1066][SCOI2007]蜥蜴（网络流）
[BZOJ 1066][SCOI2007]蜥蜴（网络流）
Description
在一个r行c列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃
到边界外。 每行每列中相邻石柱的距离为1，蜥蜴的跳跃距离是d，即蜥蜴可以跳到平面距离不超过d的任何一个石
柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减1（如果仍然落在地图内部，则到达的石柱高度不
变），如果该石柱原来高度为1，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同一个
石柱上。
Solution
把点拆成一个入点一个出点，之间连一条容量为高度的边作为限制
源向蜥蜴连容量为1的边，每个点能到达的地方由出点向入点连INF的边，能跳到汇的点向汇连INF的边
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<queue>#include<cmath>#define eps 1e-9#define INF 0x3f3f3f3f#define pos(x,y) ((x-1)*c+y)using namespace std;int r,c,d,s,t,head[1000],level[1000],cnt=0,liz=0;struct Node{ int next,to,cap;}Edges[100005];void addedge(int u,int v,int c){ Edges[cnt].next=head[u]; head[u]=cnt; Edges[cnt].to=v; Edges[cnt].cap=c; cnt++;}void insert(int u,int v,int c){ addedge(u,v,c); addedge(v,u,0);}int dcmp(double x){ if(fabs(x)<=eps)return 0; return x>0?1:-1; }double dis(int x1,int y1,int x2,int y2){ return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));}bool bfs(){ memset(level,-1,sizeof(level)); level[s]=0; queue<int>q; q.push(s); while(!q.empty()) { int u=q.front();q.pop(); for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(level[v]==-1&&Edges[i].cap) {level[v]=level[u]+1;q.push(v);} } } if(level[t]==-1)return false; return true;}int dfs(int u,int flow){ int f=0,d=0; if(u==t)return flow; for(int i=head[u];~i&&f<flow;i=Edges[i].next) { int v=Edges[i].to; if(level[v]==level[u]+1&&Edges[i].cap) { d=dfs(v,min(Edges[i].cap,flow-f)); Edges[i].cap-=d; Edges[i^1].cap+=d; f+=d; } } if(!f)level[u]=-1; return f;}int main(){ memset(head,-1,sizeof(head)); scanf("%d%d%d",&r,&c,&d); s=0,t=r*c*2+1; char S[30][30]; for(int i=1;i<=r;i++) { scanf("%s",S[i]+1); for(int j=1;j<=c;j++) { if(S[i][j]==‘0‘)continue; insert(pos(i,j),r*c+pos(i,j),S[i][j]-‘0‘); for(int k=max(i-d,1);k<=min(i+d,r);k++) for(int l=max(j-d,1);l<=min(j+d,c);l++) { if(k==i&&l==j)continue; if(S[k][l]==‘0‘)continue; if(dcmp(dis(i,j,k,l)-d)<=0) insert(r*c+pos(i,j),pos(k,l),INF); } if(i<=d||i+d>r||j<=d||j+d>c) insert(r*c+pos(i,j),t,INF); } } for(int i=1;i<=r;i++) { scanf("%s",S[i]+1); for(int j=1;j<=c;j++) { if(S[i][j]==‘L‘) ++liz,insert(s,pos(i,j),1); } } int ans=liz,d=0; while(bfs()) { while(d=dfs(s,INF)) ans-=d; } printf("%d\n",ans); return 0;}
[BZOJ 1066][SCOI2007]蜥蜴（网络流）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。