[HNOI2007]紧急疏散evacuate
时间限制: 1 Sec 内存限制: 128 MB提交: 60 解决: 10题目描述
发生了火警，所有人员需要紧急疏散！假设每个房间是一个N M的矩形区域。每个格子如果是"."，那么表示这是一块空地；如果是"X"，那么表示这是一面墙，如果是"D"，那么表示这是一扇门，人们可以从这儿撤出房间。已知门一定在房间的边界上，并且边界上不会有空地。最初，每块空地上都有一个人，在疏散的时候，每一秒钟每个人都可以向上下左右四个方向移动一格，当然他也可以站着不动。疏散开始后，每块空地上就没有人数限制了（也就是说每块空地可以同时站无数个人）。但是，由于门很窄，每一秒钟只能有一个人移动到门的位置，一旦移动到门的位置，就表示他已经安全撤离了。现在的问题是：如果希望所有的人安全撤离，最短需要多少时间？或者告知根本不可能。
输入
输入文件第一行是由空格隔开的一对正整数N与M，3<=N <=20，3<=M<=20，以下N行M列描述一个N M的矩阵。其中的元素可为字符"."、"X"和"D"，且字符间无空格。
输出
只有一个整数K，表示让所有人安全撤离的最短时间，如果不可能撤离，那么输出"impossible"（不包括引号）。
样例输入
5 5 XXXXXX...DXX.XXX..XXXXDXX
样例输出
3
提示
solution
这道题就是典型的网络流拆点，因为在每一时刻每一个门都能都能出去一个人，假设一个人到一个门的距离为x，那么他可以在x这个时间点以后，从这个门出去，就把门拆成不同的时间点，然后就可以二分总时间，然后把这个人与这个门从x到枚举的时间连一个流量为1的边，把所有的人与所有的门都这么处理，再把每一时刻的门与汇点连一条流量为1的边，在源点与每个人连一条流量为一的边，这样就能保证每个人只出去一次，每一时刻的门只出去一个人，之后在二分判断的时候，若最大流小于总人数返回非，大于等于总人数就返回真；
在间的时候可以吧不同时刻的门看成一个矩阵，这样既可以根据行列性质直接算出他们的标号，然后根据之前有的标号，同意加上一个值避免重复即可
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #define INF 1000000 9 using namespace std; 10 11 int zhao; 12 int n,m,peo; 13 int a[30][30]; 14 int dor[30]; 15 int id[30][30]; 16 int dis[410][410]; 17 int mov[6][3]; 18 int jia; 19 int S,T; 20 21 struct node{ 22 int u,v,w,nxt; 23 }g[5000100]; 24 int adj[5000100],e; 25 void add(int u,int v,int w){ 26 g[e].v=v; g[e].u=u; g[e].w=w; 27 g[e].nxt=adj[u]; adj[u]=e++; 28 } 29 bool Jud(int x,int y,int i,int pos){ 30 int x1=x+mov[i][0] ,y1=y+mov[i][1]; 31 if(!(x1>=1 && x1<=n && y1>=1 && y1<=m)) return 0; 32 if(a[x1][y1]==0 || a[x1][y1]==2) return 0; 33 int pos2=(x+mov[i][0]-1)*m+ ( y+mov[i][1] ); 34 if(dis[pos2][pos]<10000) return 0; 35 return 1; 36 } 37 void find_short(int pos){ 38 queue q; 39 q.push(pos); 40 dis[pos][pos]=0; 41 int k; 42 int x,y; 43 while(!q.empty()){ 44 k=q.front(); q.pop(); 45 //cout<<"k== "< <