Escape
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 521 Accepted Submission(s): 101
first one escape from the classroom after the class finishes. He is very proud of this fact.
One day, loneknight is day dreaming in class, and planning the shortest path for escaping. Suddently, an issue come into his mind, if everyone in the classroom want to escape as soon as possible just as loneknight, what will happend? As a kind man, loneknight
want to plan a strategy that will let everyone escape from the classroom with minimum time consume. But after dozens of minutes of consideration, loneknight find this problem so difficult for him.
Now, as the best friend of him, please design a algorithm to solve this problem for him. Note that, at every time unit, everyone can move seperately up, down, left, right one unit, or stay in the old position. In addtion, no one can move to a wall or out of
the room, the only way to escape is go through a gate. Moreover, at every time unit, a position can only contain a person, including gates. That means if in time t, a person escape thourgh gate g, no one can go into g in time t, but can go into g in t + 1.
Now, it's your job to calculate the minimum time required to escape for everyone.
place, X for human, # for wall, @ for gate). Input is end with EOF.
4 4 .@.. .X.. .... .... 4 4 .@.. .XX. .XX. ..@. 4 4 .@.. .#.. #X#. .#..
1 2 -1
分析：这题可以用最大流来解决，一开始构图有点错误，后来改了一下，是对的，不过wa了两次。。。检查好久才发现，判断不可行的情况时，数组开小了。。。
具体构图如下：
A: 增加源点src，和汇点dest，然后根据每个时间点建出分层图，每个时间对应一层，对于每层图的构造如下
B:给每个格子标上号Xi， 由于每个格子一次只能占一人，所以把每个格子分为两个点xa，xb，连上容量为1的有向边，对于格子为‘X’的，（如果为第0层的话）在源点src与xa之间连一条容量为1的有向边，对于格子为'@'的点，在xb与汇点dest连上容量为1的有向边，对于每个格子，（除‘#’外），在xb与其上下左右及其本身 的对应下一层图的xa连上容量为1
的一条有向边
C:具体操作并不是一下子建出分层图，由于时间是未知的，所以枚举时间，做最大流，当最大流小于人数时，时间加一并在原图上增加一层，继续求最大流，直到最大流大于等于人数，这时的时间就是答案
最后随便拿个模板就能A掉了。。。，本人只会Dinic。。。
代码：
#include<cstdio>
using namespace std;
const int mm=1111111;
const int mn=111111;
const int oo=1000000000;
const int dx[4]= {0,1,0,-1};
const int dy[4]= {1,0,-1,0};
int node,src,dest,edge,ret;
int reach[mm],flow[mm],next[mm];
int head[mn],work[mn],dis[mn],q[mn];
char map[22][22];
int mark[22][22],d[22][22],qx[mn],qy[mn];
int i,j,k,n,m,x,y,t,ans,num;
inline int min(int a,int b)
{
return a<b?a:b;
}
inline void addedge(int u,int v,int c)
{
reach[edge]=v,flow[edge]=c,next[edge]=head[u],head[u]=edge++;
reach[edge]=u,flow[edge]=0,next[edge]=head[v],head[v]=edge++;
}
inline void makegraph(int c,int dd)
{
int i,j,k,w=node-2;
while(dd--)head[node++]=-1;
for(i=1; i<=n; ++i)
for(j=1; j<=m; ++j)
if(mark[i][j])
{
addedge(w+mark[i][j],w+mark[i][j]+t,1);
if(!c&&map[i][j]=='X')addedge(src,w+mark[i][j],1);
if(c)
{
addedge(w-t+mark[i][j],w+mark[i][j],1);
if(map[i][j]=='@')addedge(w+mark[i][j]+t,dest,1);
for(k=0; k<4; ++k)
{
x=i+dx[k];
y=j+dy[k];
if(x>0&&x<=n&&y>0&&y<=m&&mark[x][y])
addedge(w+mark[x][y]-t,w+mark[i][j],1);
}
}
}
}
bool Dinic_bfs()
{
int i,u,v,l,r=0;
for(i=0; i<node; ++i)dis[i]=-1;
dis[q[r++]=src]=0;
for(l=0; l<r; ++l)
for(i=head[u=q[l]]; i>=0; i=next[i])
if(flow[i]&&dis[v=reach[i]]<0)
{
dis[q[r++]=v]=dis[u]+1;
if(v==dest)return 1;
}
return 0;
}
int Dinic_dfs(int u,int exp)
{
if(u==dest)return exp;
for(int &i=work[u],v,tmp; i>=0; i=next[i])
if(flow[i]&&dis[v=reach[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
{
flow[i]-=tmp;
flow[i^1]+=tmp;
return tmp;
}
return 0;
}
int Dinic_flow()
{
int i,delta;
while(Dinic_bfs())
{
for(i=0; i<node; ++i)work[i]=head[i];
while(delta=Dinic_dfs(src,oo))ret+=delta;
}
return ret;
}
void bfs(int r)
{
int i,l;
for(l=0; l<r; ++l)
for(i=0; i<4; ++i)
{
x=qx[l]+dx[i];
y=qy[l]+dy[i];
if(x>0&&x<=n&&y>0&&y<=m&&map[x][y]!='#'&&d[x][y]<0)
qx[r]=x,qy[r]=y,d[x][y]=d[qx[l]][qy[l]]+1,++r;
}
}
bool ok()
{
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j)
if(map[i][j]=='X'&&d[i][j]<0)return 0;
return 1;
}
int main()
{
while(scanf("%d%d",&n,&m)!=-1)
{
for(t=0,i=1; i<=n; ++i)
for(getchar(),j=1; j<=m; ++j)
{
map[i][j]=getchar();
mark[i][j]=0;
if(map[i][j]!='#')mark[i][j]=(++t)+1;
}
for(k=0,i=1; i<=n; ++i)
for(j=1; j<=m; ++j)
if(map[i][j]=='@')qx[k]=i,qy[k]=j,d[i][j]=0,++k;
else d[i][j]=-1;
bfs(k);
if(!ok())
{
printf("-1\n");
continue;
}
for(num=0,i=1; i<=n; ++i)
for(j=1; j<=m; ++j)
if(map[i][j]=='X')++num;
ans=ret=0;
head[0]=head[1]=-1;
node=2,src=0,dest=1;
makegraph(0,t*2);
while(Dinic_flow()<num)makegraph(1,t*2),++ans;
printf("%d\n",ans);
}
return 0;
}