[HNOI2007]紧急疏散EVACUATE
题目描述
发生了火警,所有人员需要紧急疏散!假设每个房间是一个N M的矩形区域。每个格子如果是'.',那么表示这是一块空地;如果是'X',那么表示这是一面墙,如果是'D',那么表示这是一扇门,人们可以从这儿撤出房间。已知门一定在房间的边界上,并且边界上不会有空地。最初,每块空地上都有一个人,在疏散的时候,每一秒钟每个人都可以向上下左右四个方向移动一格,当然他也可以站着不动。疏散开始后,每块空地上就没有人数限制了(也就是说每块空地可以同时站无数个人)。但是,由于门很窄,每一秒钟只能有一个人移动到门的位置,一旦移动到门的位置,就表示他已经安全撤离了。现在的问题是:如果希望所有的人安全撤离,最短需要多少时间?或者告知根本不可能。
输入输出格式
输入格式:
输入文件第一行是由空格隔开的一对正整数N与M,3<=N <=20,3<=M<=20,以下N行M列描述一个N M的矩阵。其中的元素可为字符'.'、'X'和'D',且字符间无空格。
输出格式:
只有一个整数K,表示让所有人安全撤离的最短时间,如果不可能撤离,那么输出'impossible'(不包括引号)。
输入输出样例
5 5XXXXXX...DXX.XXX..XXXXDXX
3
说明
2015.1.12新加数据一组,鸣谢1756500824
C++语言请用scanf("%s",s)读入!
题解:
这是一道二分答案与网络流算法的结合的题目,小编也是头一次做这样的题目,所以被坑了很久。
一开始没有什么头绪,后来才发现可以先SPFA一下每一个点到门的距离(也就是时间),然后二分时间求解。
1.这道题可以考虑拆点,也可以考虑拆门,显然拆门更简单,于是就果断将每一个门拆成mid个不同的点,如果一个点可以在mid时间内到达一个门d,那么就将这个点和d的mid分点连在一起。
2.虚拟一个汇点和每一个门连一条流量为1的边,虚拟一个源点和每一个点连一条流量为1的边,其余的边流量为最大值。(这样就保证了同一时间只有一个人可以通过一扇门)
3.然后不断地跑Dinic求最大流。如果可行则说明在mid时间时可以逃生,r=mid-1,如果不可行则l=mid+1。(普通的二分答案)
需要注意的地方:
1.size的初值为奇数,不然就没法跑Dinic。
2.数组的大小。(本人运行错误了好多次,所以代码中的数组开得比较大,实际上不需要这么多)
好了,应该可以上代码了:
#include#include #include #include #include #include #include #include #include #include using namespace std;const int inf=233;int n,m;int place[201][301],depth[40001],map[40001],dis[1001][1001],root,g,sum,q[501][40001],flow=0;int xx[40001],yy[40001],t[5]={ 1,0,-1,0,1};int head[40001],size;struct Edge{ int next,to,dis;}edge[100001];int b[40001];vector p;int read(){ char i=getchar();int ans=0,f=1; while(i<'0'||i>'9')if(i=='-')f=-1,i=getchar(); while(i>='0'&&i<='9')ans=ans*10+i-'0',i=getchar(); return ans*f;}void spfa(int x,int y){ int i,j,head=0,tail=0; xx[tail]=x;yy[tail++]=y; for(i=1;i<=g;i++)dis[place[x][y]][i]=inf; dis[place[x][y]][place[x][y]]=0; while(head!=tail) { int xxx=xx[head],yyy=yy[head++]; for(i=0;i<4;i++) { int nx=xxx+t[i],ny=yyy+t[i+1]; if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&map[place[nx][ny]]&&dis[place[x][y]][place[nx][ny]]>dis[place[x][y]][place[xxx][yyy]]+1) { dis[place[x][y]][place[nx][ny]]=dis[place[x][y]][place[xxx][yyy]]+1; if(map[place[nx][ny]]==1) { xx[tail]=nx; yy[tail++]=ny; } } } }}void putin(int from,int to,int dis){ size++; edge[size].next=head[from]; edge[size].to=to; edge[size].dis=dis; head[from]=size;}void in(int from,int to,int dis){ putin(from,to,dis); putin(to,from,0);}bool bfs(){ int i; for(i=root;i<=g;i++)depth[i]=0; int top=0,tail=0; b[tail++]=root;depth[root]=1; while(top!=tail) { int x=b[top++]; if(x==g)return 1; for(i=head[x];i;i=edge[i].next) { int y=edge[i].to; if(depth[y]==0&&edge[i].dis) { depth[y]=depth[x]+1; b[tail++]=y; } } } return 0;}int dfs(int root,int mmax){ int i; if(root==g)return mmax; int rev=0; for(i=head[root];i;i=edge[i].next) { int y=edge[i].to,x=edge[i].dis; if(depth[y]==depth[root]+1&&x) { int mmin=min(mmax-rev,x); x=dfs(y,mmin); edge[i].dis-=x; edge[i^1].dis+=x; rev+=x; if(rev==mmax)break; } } return rev;}bool judge(int mid){ memset(head,0,sizeof(head)); size=1; g=sum; int i,j,k; for(i=0;i >1; if(judge(mid))r=mid-1,ans=mid; else l=mid+1; } if(ans==inf)printf("impossible"); else printf("%d\n",ans); return 0;}
总结:
1.可以用place[i][j]将二维数组中的每一个位置降成一维的,方便求解。
2.输入字符串时用scanf("%S",ch+1);来避免第一位的下标是0的情况。(根据个人习惯)
3.一定要注意数组大小。(不大不小,才是王道)