首页 > 代码库 > BZOJ1189 HNOI2007 紧急疏散evacuate 网络流+BFS+二分法
BZOJ1189 HNOI2007 紧急疏散evacuate 网络流+BFS+二分法
题意：一个N M的矩形区域。格子如果是‘.‘，那么表示这是一块空地；如果是‘X‘，那么表示这是一面墙，如果是‘D‘，那么表示这是一扇门，人们可以从这儿撤出房间。已知门一定在房间的边界上，并且边界上不会有空地。每块空地上都有一个人，在疏散的时候，每一秒钟每个人都可以向上下左右四个方向移动一格，当然他也可以站着不动。疏散开始后，每块空地上就没有人数限制。每一秒钟只能有一个人移动到门的位置，一旦移动到门的位置，就表示他已经安全撤离了。求所有的人安全撤离，最短需要多少时间
题解：
好神啊这题……
首先我们用BFS跑出每个门到每个以可以到达的点的最小时间，然后二分答案x，从每个门向汇点连一条容量x的边，从源点向每个空地连边，空地向能在x时间内能到达的每一个门连边，跑最大流检验即可。
（实际上这个算法是错误的，因为无法限制每一秒之能有一个人通过，因而需要把每个门都拆成x个门，x-1向x连边，每个拆出来的点向汇点连一条容量为一的边。啊好麻烦懒得写了，谁叫数据水呢QAQ）
#include <queue>#include <vector>#include <cstdio>#include <climits>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;#define NODE pair<int,int>const int T=1000+2;const int U=400+2;const int MAXN=30+2;const int MAXK=60000+2;const int MAXM=3000000+2;const int X[]={-1,0,1,0};const int Y[]={0,1,0,-1};struct EDGE{ int u,c; EDGE(){} EDGE(int _u,int _c):u(_u),c(_c){}}e[MAXM];int N,M,D=1,ans=-1,sum,dist[MAXN][MAXN][MAXN],g[MAXN][MAXN],d[MAXK],cur[MAXK],cnt;char S[MAXN][MAXM];queue<int> q2;queue<NODE> q1;vector<int> tab[MAXK];void Insert(int u,int v,int c){ tab[u].push_back(cnt),e[cnt++]=EDGE(v,c); tab[v].push_back(cnt),e[cnt++]=EDGE(u,0);}bool Check(int x,int y){ if(!x || !y) return 0; if(x>N || y>M) return 0; return g[x][y]==1;}void Find(int k,int x,int y){ q1.push(make_pair(x,y)),dist[k][x][y]=0; NODE t; while(!q1.empty()){ t=q1.front(),q1.pop(); for(int i=0;i<4;i++) if(Check(t.first+X[i],t.second+Y[i]) && dist[k][t.first+X[i]][t.second+Y[i]]>dist[k][t.first][t.second]+1){ dist[k][t.first+X[i]][t.second+Y[i]]=dist[k][t.first][t.second]+1; q1.push(make_pair(t.first+X[i],t.second+Y[i])); } }}void Build(int x){ cnt=0; for(int i=1;i<=T;i++) tab[i].clear(); for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) if(g[i][j]==1) Insert(0,(i-1)*M+j,1); for(int i=2;i<=D;i++) Insert(N*M+i,T,x); for(int i=2;i<=D;i++) for(int j=1;j<=N;j++) for(int k=1;k<=M;k++) if(dist[i][j][k]<=x) Insert((j-1)*M+k,N*M+i,x);}bool BFS(int s,int t){ memset(d,-1,sizeof(d)); d[s]=0,q2.push(s); int x; while(!q2.empty()){ x=q2.front(),q2.pop(); for(int i=0;i<tab[x].size();i++) if(e[tab[x][i]].c && d[e[tab[x][i]].u]==-1) d[e[tab[x][i]].u]=d[x]+1,q2.push(e[tab[x][i]].u); } return d[t]>0;}int DFS(int x,int f,int t){ if(x==t) return f; int flow,used=0; for(int i=cur[x];i<tab[x].size();i++) if(e[tab[x][i]].c && d[e[tab[x][i]].u]==d[x]+1){ flow=DFS(e[tab[x][i]].u,min(f-used,e[tab[x][i]].c),t); e[tab[x][i]].c-=flow,e[tab[x][i]^1].c+=flow,used+=flow; if(e[tab[x][i]].c) cur[x]=i; if(used==f) return f; } if(!used) d[x]=-1; return used;}int Dinic(int s,int t){ int ret=0; while(BFS(s,t)){ memset(cur,0,sizeof(cur)); ret+=DFS(s,INT_MAX,t); } return ret;}bool Judge(int x){ Build(x); return Dinic(0,T)==sum;}int main(){ scanf("%d %d",&N,&M); for(int i=1;i<=N;i++) scanf("%s",S[i]+1); for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) if(S[i][j]==‘.‘) g[i][j]=1,sum++; else if(S[i][j]==‘D‘) g[i][j]=++D; memset(dist,0X7F,sizeof(dist)); for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) if(g[i][j]>1) Find(g[i][j],i,j); int l=1,r=U,m; while(l<=r){ m=(l+r)>>1; if(Judge(m)) ans=m,r=m-1; else l=m+1; } if(ans==-1) printf("impossible\n"); else printf("%d\n",ans); return 0;}
BZOJ1189 HNOI2007 紧急疏散evacuate 网络流+BFS+二分法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。