绝世污题，垃圾题，浪费我一整天青春！
1189: [HNOI2007]紧急疏散evacuate
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1262 Solved: 464
[Submit][Status][Discuss]
Description
发生了火警，所有人员需要紧急疏散！假设每个房间是一个N M的矩形区域。每个格子如果是’.’，那么表示这是一块空地；如果是’X’，那么表示这是一面墙，如果是’D’，那么表示这是一扇门，人们可以从这儿撤出房间。已知门一定在房间的边界上，并且边界上不会有空地。最初，每块空地上都有一个人，在疏散的时候，每一秒钟每个人都可以向上下左右四个方向移动一格，当然他也可以站着不动。疏散开始后，每块空地上就没有人数限制了（也就是说每块空地可以同时站无数个人）。但是，由于门很窄，每一秒钟只能有一个人移动到门的位置，一旦移动到门的位置，就表示他已经安全撤离了。现在的问题是：如果希望所有的人安全撤离，最短需要多少时间？或者告知根本不可能。
Input
输入文件第一行是由空格隔开的一对正整数N与M，3<=N <=20，3<=M<=20，以下N行M列描述一个N M的矩阵。其中的元素可为字符’.’、’X’和’D’，且字符间无空格。
Output
只有一个整数K，表示让所有人安全撤离的最短时间，如果不可能撤离，那么输出’impossible’（不包括引号）。
Sample Input
5 5
XXXXX
X…D
XX.XX
X..XX
XXDXX
Sample Output
3
HINT
Source
这道题绝对污的不行，第一次尝试自己理想建图，崩烂；
第二次修改时走投无路上网看解析，在评论的指引下发现网上神犇学长的建图都忽略了**每单位时间每个门只能走一个人**这一点，实现后发现数据水，能过
但是在与YveH爷和HZWer学长的交谈中对正确建模有了想法；
第三次尝试正解，又搞了半天╮(╯▽╰)╭最后10组数据，9组一共跑了不到1s，极限数据一组4.5s。。（还好bzoj测总时间）
建图如下（神级建图）：
1.BFS预处理出每个’.’到每个’D’的曼哈顿距离（最短移动时间）
2.二分最短总时间，mint
3.把每个’D’按时间拆点，即把每个’D’都拆成mint个点
4.判断这个’.’到这个’D’的时间是否<=mint，满足则将这个’.’与拆后的’D’的点连边（从这个’.’到’D’的所需时间到拆成的最后一个点都要连边）边权为1 ；
PS：这里的意思就是二分出的mint，把每个’D’都拆成mint个点，假如这个’.’到这个’D’的时间为t，且t
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int dis[1100000];
struct data{
int next,to,v;
}edge[1100100];
int head[1000100],cnt;
int n,m;
int rnum=0,dnum=0;
int q[200010],h,t;
int mt[410][25][25]={0};
struct data1{
int x,y,step;
};
bool can[25][25]={0};
bool visit[25][25]={false};
int move[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
int cs[25][25]={0};
int num;
void add(int u,int v,int w)
{
cnt++;
edge[cnt].v=w;
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
void insert(int u,int v,int w)
{
add(u,v,w);add(v,u,0);
}
void sear(int nowx,int nowy)
{
queue<data1> que;
int p=-cs[nowx][nowy];//cs【】【】里门的序号是存的负数。。
que.push({nowx,nowy,0});
while (!que.empty())
{
data1 temp=que.front();
que.pop();
int x=temp.x;
int y=temp.y;
int deep=temp.step;
visit[x][y]=true;
for (int i=0;i<4;i++)
if (!visit[x+move[i][0]][y+move[i][1]] && cs[x+move[i][0]][y+move[i][1]]>0 &&
x+move[i][0]>=1 && x+move[i][0]<=n && y+move[i][1]>=1 && y+move[i][1]<=m)
que.push({x+move[i][0],y+move[i][1],deep+1});
mt[p][x][y]=deep;
can[x][y]=1;//can【】【】记录这个点能不能走到门
}
}//预处理出每个'.'到每个'D'的距离
void init()
{
scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++)
{
char x[25];
scanf("%s",&x);
for (int j=1; j<=m; j++)
{
if (x[j-1]=='.') {rnum++;cs[i][j]=rnum;}
if (x[j-1]=='X') cs[i][j]=0;
if (x[j-1]=='D') {dnum++;cs[i][j]=-dnum;}
}
}//rnum表示人数，dnum表示门数（总之可以理解为>0的是人，=0的是墙，<0的是门）
memset(mt,0x3f,sizeof(mt));
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
if (cs[i][j]<0)
{
memset(visit,false,sizeof(visit));
sear(i,j);
}//遇到门就BFS出能到这个门的各个点的距离
}
void make(int mint)
{
cnt=1;memset(head,0,sizeof(head));
for (int i=1; i<=dnum; i++)
for (int j=1; j<=n; j++)
for (int k=1; k<=m; k++)
if (cs[j][k]>0 && mt[i][j][k]<=mint)
for (int l=mt[i][j][k]; l<=mint; l++)
insert((j-1)*m+k,n*m*i+l,1);//点到拆过后的门的连边
for (int i=1; i<=dnum; i++)
for (int j=1; j<=mint; j++)
insert(n*m*i+j,n*m*(dnum+1)+1,1);//拆过后的门到超级汇连边
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
if (can[i][j] && cs[i][j]>0)
insert(0,(i-1)*m+j,1);//超级源到个点连边
num=n*m*(dnum+1)+1;
}
bool bfs()
{
memset(dis,-1,sizeof(dis));
q[1]=0; dis[0]=1;
h=0;t=1;
while (h<t)
{
int j=q[++h],i=head[j];
while (i)
{
if (edge[i].v>0 && dis[edge[i].to]<0)
{
dis[edge[i].to]=dis[j]+1;
q[++t]=edge[i].to;
}
i=edge[i].next;
}
}
if (dis[num]>0)
return true;
else
return false;
}
int dfs(int loc,int low)
{
int i=head[loc];
if (loc==num) return low;
while (i)
{
int flow=0;
if (edge[i].v>0 && dis[edge[i].to]==dis[loc]+1 && (flow=dfs(edge[i].to,min(edge[i].v,low))))
{
edge[i].v-=flow;
edge[i^1].v+=flow;
return flow;
}
i=edge[i].next;
}
return 0;
}
int main()
{
init();
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
if (cs[i][j]>0 && !can[i][j]) {printf("impossible");return 0;}//如果有人不能走到门则impossible
int left=0,right=n*m;
while (left<=right)
{
int mid=(left+right)>>1;
make(mid);
int ans=0;
while (bfs())
{
int now;
while ((now=dfs(0,0x7fffffff)))
ans+=now;
}
if (ans<rnum) left=mid+1;
else right=mid-1;
}
printf("%d\n",left);
return 0;
}