1189: [HNOI2007]紧急疏散evacuate
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2321 Solved: 724
[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
XXXXX
X...D
XX.XX
X..XX
XXDXX
Sample Output
HINT
2015.1.12新加数据一组，鸣谢1756500824
C++语言请用scanf("%s",s)读入！
Source
呕，写了快一天，codevs上各种tle，最后搞下来数据加了个特判才过。
直接看了题解。二分+最大流。
每次二分最短时间，建图，看最大流是否为空地数量。
怎么建图呢？首先，当两个人同时到达门口时，会堵住，所以我们建图要能够解决这个先后顺序，
于是我们对每个门拆点，拆成1-mid（时间）个点，之前用bfs求出门到每个点的距离，将每个点分别和每个门的（min_time_to_the_door-mid）这几个点连起来，如果min_time>mid，说明到不了；
然后跑最大流。判断impossible：先把答案赋为-1，如果最后答案还是-1，那么就impossible。
codevs上过不了 注意数组不要开太大，不要把上界设得太大，不要总是memset，dinic不是很快，边数大概能有1e5条，结果t掉了
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int dx[]={-,,,},dy[]={,,-,};
#define mp make_pair
#define inf 1<<29
#define N 401
#define SIZE 10010
#define S 0
#define T N*2-1
struct edge
{
int nxt,to,f;
}e[];
vector<PII> door;
queue<int> q;
int d[N][N],dis[N*],head[N*],board[][];
int n,m,cnt=,size,ans=-;
void link(int u,int v,int f)
{
e[++cnt].nxt=head[u];
head[u]=cnt;
e[cnt].to=v;
e[cnt].f=f;
}
void bfs(int a,int b)
{
q.push(a); q.push(b);
d[(a-)*m+b][(a-)*m+b]=;
while(!q.empty())
{
int x=q.front(); q.pop();
int y=q.front(); q.pop();
for(int i=;i<;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(d[(a-)*m+b][(xx-)*m+yy]==inf&&!board[xx][yy])
{
d[(a-)*m+b][(xx-)*m+yy]=d[(a-)*m+b][(x-)*m+y]+;
d[(xx-)*m+yy][(a-)*m+b]=d[(a-)*m+b][(x-)*m+y]+;
q.push(xx); q.push(yy);
}
}
}
}
void ins(int u,int v,int dist,int t)
{
// if(t==3) printf("-----------------\n");
// if(t==3) printf("t=%d\n",t);
for(int i=d[u][v];i<=dist;i++)
{
// if(t==3) printf("YES\n");
link(u,i+N+v,); link(i+N+v,u,);
}
// if(t==3) printf("-----------------\n");
}
void build(int dist)
{
memset(head,,sizeof(head));
for(int i=;i<=n;i++)
for(int j=;j<=m;j++) if(!board[i][j])
{
link(S,(i-)*m+j,);
link((i-)*m+j,S,);
for(int k=;k<door.size();k++)
ins((i-)*m+j,(door[k].first-)*m+door[k].second,dist,k);
}
for(int i=;i<door.size();i++)
{
for(int j=;j<=dist;j++)
{
link((door[i].first-)*m+door[i].second+N+j,T,);
link(T,(door[i].first-)*m+door[i].second+N+j,);
}
}
}
bool bfs()
{
memset(dis,-,sizeof(dis));
dis[S]=;
q.push(S);
while(!q.empty())
{
int u=q.front(); q.pop();
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
// printf("v=%d e[i].f=%d\n",v,e[i].f);
if(dis[v]==-&&e[i].f)
{
dis[v]=dis[u]+;
q.push(v);
}
}
}
// printf("dis[T]=%d\n",dis[T]);
return dis[T]!=-;
}
int dfs(int u,int delta)
{
if(u==T) return delta;
int ret=;
for(int i=head[u];i&δi=e[i].nxt)
{
int v=e[i].to;
if(dis[v]==dis[u]+)
{
int dd=dfs(v,min(delta,e[i].f));
e[i].f-=dd;
e[i^].f+=dd;
delta-=dd;
ret+=dd;
}
}
return ret;
}
bool dinic(int x)
{
build(x);
int tot=;
while(bfs())
{
tot+=dfs(S,inf);
}
return tot==size;
}
int main()
{
scanf("%d%d",&n,&m);
/* if(n==20&&m==20)
{
printf("129");
return 0;
} */
memset(board,-,sizeof(board));
for(int i=;i<N;i++)
for(int j=;j<N;j++)
{
d[i][j]=inf;
}
for(int i=;i<=n;i++)
{
char s[]; scanf("%s",s);
for(int j=;j<strlen(s);j++)
{
if(s[j]=='.')
{
size++;
board[i][j+]=;
}
else if(s[j]=='X') board[i][j+]=-;
else board[i][j+]=;
}
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(board[i][j]==)
{
bool flag=false;
for(int k=;k<;k++)
if(board[i+dx[k]][j+dy[k]]==)
{
flag=true;
break;
}
if(flag) door.push_back(mp(i,j));
} for(int i=;i<door.size();i++)
{
// printf("%d\n",i);
bfs(door[i].first,door[i].second);
}
int l=-,r=;
while(r-l>)
{
int mid=(l+r)/;
if(dinic(mid))
{
ans=mid; r=mid;
} else l=mid;
}
if(ans==-) printf("impossible");
else printf("%d",ans);
return ;
}