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
XXXXX
X...D
XX.XX
X..XX
XXDXX
Sample Output
3
题解
话说搜索可以骗70分，考虑一群人可以从几个门出去，去个平均数，不能整除则加1，取每一块的最大值。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,tot,peop,usd,mark[22][22],bs[22][22],ans=-1;
char map[22][22];
struct message{int x,y;} d[105],q[405];
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
void init()
{
scanf("%d%d",&n,&m);
int i,j;
for(i=0;i<n;i++)
{scanf("%s",map[i]);
for(j=0;j<m;j++)
{if(map[i][j]=='D')
{tot++; d[tot].x=i; d[tot].y=j;}
else if(map[i][j]=='.') peop++;
}
}
}
bool check(int x,int y)
{
if(x<0||y<0||x>=n||y>=m) return true;
if(map[x][y]=='X') return true;
return false;
}
void bfs(int sx,int sy)
{
int i,t=0,w=1,tx,ty,nx,ny;
int sum=0,div=1;
memset(bs,-1,sizeof(bs));
q[t].x=sx; q[t].y=sy; bs[sx][sy]=0;
while(t!=w)
{nx=q[t].x; ny=q[t].y; t=(t+1)%(n*m);
for(i=0;i<4;i++)
{tx=nx+xx[i]; ty=ny+yy[i];
if(bs[tx][ty]!=-1) continue;
if(check(tx,ty)) continue;
if(map[tx][ty]=='.')
{sum++; q[w].x=tx; q[w].y=ty; w=(w+1)%(n*m);
bs[tx][ty]=bs[nx][ny]+1;
}
else if(map[tx][ty]=='D') {div++; mark[tx][ty]=1;}
}
}
usd+=sum;
if(sum%div==0) ans=max(ans,sum/div);
else ans=max(ans,(sum/div)+1);
}
void work()
{
int i;
for(i=1;i<=tot;i++)
{if(mark[d[i].x][d[i].y]==1) continue;
mark[d[i].x][d[i].y]=1; bfs(d[i].x,d[i].y);
}
if(usd>=peop) printf("%d\n",ans);
else puts("impossible");
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
init(); work();
return 0;
}
正解二分+网络流，二分最大值，每次暴力建图即可。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define S 401
#define T 402
#define inf 1<<30
using namespace std;
int n,m,tot,peop,bs[25][25],dis[25][25][100];
char map[25][25];
struct wu{int x,y;} d[100],q[405];
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
int h[405],zz,head[405],ans,dui[405];
struct bian{int to,nx,v;} e[800000];
//------------------------------------------------------------------------------
void init()
{
scanf("%d%d",&n,&m);
int i,j;
for(i=0;i<n;i++)
{scanf("%s",map[i]);
for(j=0;j<m;j++)
{if(map[i][j]=='D')
{tot++; d[tot].x=i; d[tot].y=j;}
else if(map[i][j]=='.') peop++;
}
}
}
bool check(int x,int y)
{
if(x<0||y<0||x>=n||y>=m) return true;
if(bs[x][y]!=-1||map[x][y]=='X'||map[x][y]=='D') return true;
return false;
}
void prebfs(int sx,int sy)
{
int i,t=0,w=1,nx,ny,tx,ty;
memset(bs,-1,sizeof(bs));
q[0].x=sx; q[0].y=sy; bs[sx][sy]=0;
while(t!=w)
{nx=q[t].x; ny=q[t].y; t=(t+1)%(n*m);
for(i=0;i<4;i++)
{tx=nx+xx[i]; ty=ny+yy[i];
if(check(tx,ty)) continue;
q[w].x=tx, q[w].y=ty; w=(w+1)%(n*m);
bs[tx][ty]=bs[nx][ny]+1;
}
}
}
void pre()
{
int i,j,k;
memset(dis,127,sizeof(dis));
for(i=1;i<=tot;i++)
{prebfs(d[i].x,d[i].y);
for(j=0;j<n;j++)
for(k=0;k<m;k++)
{if(bs[j][k]!=-1) dis[j][k][i]=bs[j][k];
}
}
}
//------------------------------------------------------------------------------
void insert(int x,int y,int z)
{
zz++; e[zz].to=y; e[zz].v=z; e[zz].nx=head[x]; head[x]=zz;
zz++; e[zz].to=x; e[zz].v=0; e[zz].nx=head[y]; head[y]=zz;
}
void rebuild(int f)
{
int i,j,k,x,y;
memset(head,0,sizeof(head));
zz=1;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{if(map[i][j]!='.') continue;
x=i*m+j; insert(S,x,1);
for(k=1;k<=tot;k++)
{if(dis[i][j][k]<=f)
{y=d[k].x*m+d[k].y;
insert(x,y,1);
}
}
}
for(i=1;i<=tot;i++)
{x=d[i].x*m+d[i].y; insert(x,T,f);}
}
bool bfs()
{
memset(h,-1,sizeof(h));
int i,t=0,w=1,x,p;
h[S]=0; dui[0]=S;
while(t<w)
{x=dui[t]; t++;
for(i=head[x];i;i=e[i].nx)
{p=e[i].to;
if(h[p]<0&&e[i].v)
{h[p]=h[x]+1;
dui[w]=p; w++;
}
}
}
if(h[T]==-1) return false;
return true;
}
int dfs(int x,int f)
{
if(x==T) return f;
int usd=0,rest,p,i;
for(i=head[x];i;i=e[i].nx)
{p=e[i].to;
if(h[p]==h[x]+1&&e[i].v)
{rest=f-usd;
rest=dfs(p,min(rest,e[i].v));
e[i].v-=rest;
e[i^1].v+=rest;
usd+=rest;
if(usd==f) return f;
}
}
if(!usd) h[x]=-1;
return usd;
}
bool judge(int x)
{
rebuild(x);
int sum=0;
while(bfs()) sum+=dfs(S,inf);
if(sum==peop) return true;
else return false;
}
void work()
{
int l=1,r=peop,mid;
ans=-1;
while(l<=r)
{mid=(l+r)>>1;
if(judge(mid)) {ans=mid; r=mid-1;}
else l=mid+1;
}
if(ans==-1) puts("impossible");
else printf("%d\n",ans);
}
//------------------------------------------------------------------------------
int main()
{
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
init(); pre();
work();
return 0;
}