[HNOI2007]紧急疏散EVACUATE
题目描述
发生了火警，所有人员需要紧急疏散！假设每个房间是一个N M的矩形区域。每个格子如果是'.'，那么表示这是一块空地；如果是'X'，那么表示这是一面墙，如果是'D'，那么表示这是一扇门，人们可以从这儿撤出房间。已知门一定在房间的边界上，并且边界上不会有空地。最初，每块空地上都有一个人，在疏散的时候，每一秒钟每个人都可以向上下左右四个方向移动一格，当然他也可以站着不动。疏散开始后，每块空地上就没有人数限制了（也就是说每块空地可以同时站无数个人）。但是，由于门很窄，每一秒钟只能有一个人移动到门的位置，一旦移动到门的位置，就表示他已经安全撤离了。现在的问题是：如果希望所有的人安全撤离，最短需要多少时间？或者告知根本不可能。
输入输出格式
输入格式：
输入文件第一行是由空格隔开的一对正整数N与M，3<=N <=20，3<=M<=20，以下N行M列描述一个N M的矩阵。其中的元素可为字符'.'、'X'和'D'，且字符间无空格。
输出格式：
只有一个整数K，表示让所有人安全撤离的最短时间，如果不可能撤离，那么输出'impossible'（不包括引号）。
输入输出样例
5 5
XXXXX
X...D
XX.XX
X..XX
XXDXX
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<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
using namespace std;
const int inf=;
int n,m;
int place[][],depth[],map[],dis[][],root,g,sum,q[][],flow=;
int xx[],yy[],t[]={,,-,,};
int head[],size;
struct Edge
{
int next,to,dis;
}edge[];
int b[];
vector<int>p;
int read()
{
char i=getchar();int ans=,f=;
while(i<''||i>'')if(i=='-')f=-,i=getchar();
while(i>=''&&i<='')ans=ans*+i-'',i=getchar();
return ans*f;
}
void spfa(int x,int y)
{
int i,j,head=,tail=;
xx[tail]=x;yy[tail++]=y;
for(i=;i<=g;i++)dis[place[x][y]][i]=inf;
dis[place[x][y]][place[x][y]]=;
while(head!=tail)
{
int xxx=xx[head],yyy=yy[head++];
for(i=;i<;i++)
{
int nx=xxx+t[i],ny=yyy+t[i+];
if(nx>=&&nx<=n&&ny>=&&ny<=m&&map[place[nx][ny]]&&dis[place[x][y]][place[nx][ny]]>dis[place[x][y]][place[xxx][yyy]]+)
{
dis[place[x][y]][place[nx][ny]]=dis[place[x][y]][place[xxx][yyy]]+;
if(map[place[nx][ny]]==)
{
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,);
}
bool bfs()
{
int i;
for(i=root;i<=g;i++)depth[i]=;
int top=,tail=;
b[tail++]=root;depth[root]=;
while(top!=tail)
{
int x=b[top++];
if(x==g)return ;
for(i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if(depth[y]==&&edge[i].dis)
{
depth[y]=depth[x]+;
b[tail++]=y;
}
}
}
return ;
}
int dfs(int root,int mmax)
{
int i;
if(root==g)return mmax;
int rev=;
for(i=head[root];i;i=edge[i].next)
{
int y=edge[i].to,x=edge[i].dis;
if(depth[y]==depth[root]+&&x)
{
int mmin=min(mmax-rev,x);
x=dfs(y,mmin);
edge[i].dis-=x;
edge[i^].dis+=x;
rev+=x;
if(rev==mmax)break;
}
}
return rev;
}
bool judge(int mid)
{
memset(head,,sizeof(head));
size=;
g=sum;
int i,j,k;
for(i=;i<p.size();i++)
for(j=;j<=mid;j++)
q[p[i]][j]=++g;
g++;
for(i=;i<p.size();i++)
for(j=;j<=mid;j++)
{
in(q[p[i]][j],g,);
if(j!=mid)in(q[p[i]][j],q[p[i]][j+],inf);
}
int ret=;
for(i=;i<=n;i++)
{
for(j=;j<=m;j++)
{
if(map[place[i][j]]==)
{
ret++;
in(root,place[i][j],);
for(k=;k<p.size();k++)
{
if(dis[place[i][j]][p[k]]<=mid)
{
in(place[i][j],q[p[k]][dis[place[i][j]][p[k]]],);
}
}
}
}
}
flow=;
while(bfs())
{
flow+=dfs(root,);
}
return flow==ret;
}
int main()
{
int i,j;
n=read();m=read();
root=;
for(i=;i<=n;i++)
for(j=;j<=m;j++)
place[i][j]=++g;
sum=g;
char ch[];
for(i=;i<=n;i++)
{
scanf("%s",ch+);
for(j=;j<=m;j++)
{
if(ch[j]=='.')map[place[i][j]]=;
if(ch[j]=='D')map[place[i][j]]=,p.push_back(place[i][j]);
}
}
if(p.size()==){printf("impossible");return ;}
for(i=;i<=n;i++)
{
for(j=;j<=m;j++)
if(map[place[i][j]]==)spfa(i,j);
}
int l=,r=inf,ans=inf;
while(l<=r)
{
int mid=(l+r)>>;
if(judge(mid))r=mid-,ans=mid;
else l=mid+;
}
if(ans==inf)printf("impossible");
else printf("%d\n",ans);
return ;
}
总结：
1.可以用place[i][j]将二维数组中的每一个位置降成一维的，方便求解。
2.输入字符串时用scanf("%S",ch+1);来避免第一位的下标是0的情况。（根据个人习惯）
3.一定要注意数组大小。（不大不小，才是王道）