Prison Break

时间限制: 1 Sec 内存限制: 128 MB
提交: 105 解决: 16
[提交][状态][讨论版]

题目描述

Scofild又要策划一次越狱行动，和上次一样，他已经掌握了整个监狱的地图，看守的位置，以及准备好了逃出监狱的出口。由于消息被其他监狱中的囚犯得知了，为了不泄露消息，他不得不将所有人带出监狱。
这是一个月黑风高的夜晚。。。看守们都已经睡着，在没有罪犯打扰的情况下绝对不会醒来，即罪犯不能到达看守所在位置。在每一个空地中，都有一名罪犯，并且同一个空地，能容纳无穷多个罪犯。每个人都只能向东南西北四个方向移动。在地图中某些位置，有一些出口，当罪犯到达出口，就视为逃出监狱，并且出口每一秒钟最多能逃出1个罪犯。现在越狱行动开始。。。Scofild需要安排一个越狱计划，使得大家能尽快的逃出监狱。此时，监狱的监控发现了情况，监狱外的警察，将在T秒后到达现场，并封锁所有出口。现在Scofild想要知道所有人能否成功越狱，如果能，计算出所需的最短的越狱时间，使得最后一个人逃出监狱的时间尽量的短。

输入

第一行三个整数r，c，T（3 <= r, c <= 12）
接下来r行字符，每行c列。‘.’表示一个空地，一开始该点有一名罪犯。‘X’表示警察的位置，并且他不能移动，罪犯也不能到达该点，否则他就会醒来并拉响警报。‘E’表示出口。

输出

1行，输出最少的越狱时间，如果在大批警察赶到之后还有人无法逃离，则输出“impossible”。

样例输入

5 5 3

XXEXX

X...X

E...X

X...E

XXXXX

样例输出

这道题也许很少有人会去想二分答案，因为我看到这题的是时候没什么思路，模型转换最基础的都不会，直到zyh老师讲了一遍才知道，主要还是构图问题十分严重，

可以这样构图，求出各人犯到出口的最短路，然后就等在那里，假设有几个分身，因为出口一次只能跑出去一个人所以人到了可以等在那里，然后从那个时刻开始，

可以发现 n时刻可以全跑出，那么>n的时刻绝对可以跑出，如果n时刻不能跑出，那么n-1时刻坑定不能跑出，所以具有二分性，如何判断能不能跑完呢？就是用二分图

最大匹配数去判断，将每个出口裂成mid时刻个点，如果最短时间是t则与裂成的点，表示t，t+1,...,mid所有点连一条边，表示任何这里时刻都可以跑出，这样复杂度

O(nmlogt）是可以过的。

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<cstring>

 using namespace std;

 typedef pair<int,int>fzy;

 const int NN=*+;

 int n,m,T,ckt=,ckq=;

 int dis[NN][NN],flag[NN*],fa[NN*];

 char c[][];

 bool boo[][];

 int cb[][]={};

 struct node

 {

     int x,y,flag;

 }out[NN],qf[NN];

 int cnt,head[NN*],next[],rea[];

 void add(int u,int v)

 {

     cnt++;

     next[cnt]=head[u];

     head[u]=cnt;

     rea[cnt]=v;

 }

 bool dfs(int u)

 {

     for (int i=head[u];i!=-;i=next[i])

     {

         int v=rea[i];

         if (flag[v]==)

         {

             flag[v]=;

             if (fa[v]==-||dfs(fa[v]))

             {

                 fa[v]=u;

                 return ;

             }

         }

     }

     return ;

 }

 void bfs(int i)

 {

     queue<fzy>q;

     queue<int>p;

     memset(boo,,sizeof(boo));

     boo[qf[i].x][qf[i].y]=;

     while (!q.empty()) q.pop();

     while (!p.empty()) p.pop();

     q.push(make_pair(qf[i].x,qf[i].y));

     p.push();

     while (!q.empty())

     {

         fzy now=q.front();

         int vis=p.front();

         q.pop(),p.pop();

         int x=now.first,y=now.second;

         if (c[x][y]=='E') dis[i][cb[x][y]]=vis;

         if (x->=&&c[x-][y]!='X'&&boo[x-][y]==)

         {

             boo[x-][y]=;

             q.push(make_pair(x-,y));

             p.push(vis+);

         }

         if (x+<=n&&c[x+][y]!='X'&&boo[x+][y]==)

         {

             boo[x+][y]=;

             q.push(make_pair(x+,y));

             p.push(vis+);

         }

         if (y->=&&c[x][y-]!='X'&&boo[x][y-]==)

         {

             boo[x][y-]=;

             q.push(make_pair(x,y-));

             p.push(vis+);

         }

         if (y+<=m&&c[x][y+]!='X'&&boo[x][y+]==)

         {

             boo[x][y+]=;

             q.push(make_pair(x,y+));

             p.push(vis+);

         }

     }

 }

 int main()

 {

     scanf("%d%d%d",&n,&m,&T);

     memset(dis,-,sizeof(dis));

     for (int i=;i<=n;i++)

         scanf("%s",c[i]+);

     for (int i=;i<=n;i++)

         for (int j=;j<=m;j++)

             if (c[i][j]=='E')

             {

                 out[++ckt].flag=ckt;

                 out[ckt].x=i,out[ckt].y=j;

                 cb[i][j]=ckt;

             }

             else if (c[i][j]=='.')

                  {

                       qf[++ckq].x=i;

                       qf[ckq].y=j;

                  }

     for (int i=;i<=ckq;i++) bfs(i);

     int l=,r=T+;

     while (l<r)

     {

         int mid=(l+r)/;

         cnt=;

         memset(head,-,sizeof(head));

         for (int i=;i<=ckq;i++)

             for (int j=;j<=ckt;j++)

                 if (dis[i][j]!=-)

                 for (int k=dis[i][j];k<=mid;k++)

                     add(i,(j-)*mid+k);

         int res=;

         memset(fa,-,sizeof(fa));

         for (int i=;i<=ckq;i++)

         {

             memset(flag,,sizeof(flag));

             res+=dfs(i);

         }

         if (res==ckq) r=mid;

         else l=mid+;

     }

     if (l==)

     {

         cout<<<<endl;

         return ;

     }

     if (l==T+) printf("impossible");

     else printf("%d\n",l);

 }

巴特西

Prison Break

Prison Break

题目描述

输入

输出

样例输入

样例输出

最新文章

热门文章