题目：

Evacuation，题解-LMLPHP

题意：

　　有人，门（只有边上有，且1s只能出去一个人），和墙，每s人可移动一个格子，问多少秒所有人可以逃出，逃不出输出“impossible”

分析：

　　首先，我们先想着样一个问题，如果这个人在某一秒可以到达了这个们，他将可以在这1s之后的任一没人通过此门的时刻出门。而且题意说每个门每一刻只能使1人通过，那么我们可以直接把门分成好多门（1s一个，当然时间有上线），然后让人和这些门去匹配就好了，看一下第几秒可以人都匹配上就好了，当然我们加一个二分不要一个一个跑了，最后复杂度：10（二分）*10*10（人）*10*10（人）*44（门）*100（时间）（有些估算的较大），有点大，不过还是可以的，毕竟这样求匹配的常熟是很小的。当然有人写的是用D去匹配.然后不用二分了，但是这样的复杂度更大了，它是10*10（人）*44（门）*100（时间）*44（门）*100（时间），而且常数可能也大了。最后就是代码。

#include <cstdio>

#include <queue>

#include <cstring>

using namespace std;

char ch[][];

const int maxn=***+;

struct E{

    int to;

    int next;

    int val;

}ed[maxn];

int head[maxn],ma[maxn],tot;

bool vis[][];

void J(int a,int b,int c){

    ed[++tot].to=b;

    ed[tot].val=c;

    ed[tot].next=head[a];

    head[a]=tot;

}

struct Node{

    int x,y,t;

    Node(){}

    Node(int a,int b,int c){x=a;y=b;t=c;}

};

int x,y;

queue<Node> qu;

int dx[]={,,,-};

int dy[]={,-,,};

int M1(int a,int b){return y*(a-)+b;}

int M2(int a,int b,int t){return (M1(a,b)-)*+t;}

void JIA(int a,int b,int nx,int ny,int t){

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

        J(M1(a,b),M2(nx,ny,i),i);

}

void Bfs(int a,int b){

    memset(vis,,sizeof(vis));

    vis[a][b]=;

    qu.push(Node(a,b,));

    while(!qu.empty()){

        Node js=qu.front();

        qu.pop();

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

            int nx=js.x+dx[i],ny=js.y+dy[i];

            if(nx>=&&nx<=x&&ny>=&&ny<=y&&!vis[nx][ny]&&ch[nx][ny]=='.'){

                vis[nx][ny]=;

                qu.push(Node(nx,ny,js.t+));

            }

            if(nx>=&&nx<=x&&ny>=&&ny<=y&&!vis[nx][ny]&&ch[nx][ny]=='D'){

                vis[nx][ny]=;

                JIA(a,b,nx,ny,js.t+);

            }

        }

    }

}

bool vis2[maxn];

bool Dfs(int x,int t){

    for(int i=head[x];i;i=ed[i].next){

        if(vis2[ed[i].to]||ed[i].val>t) continue;

        vis2[ed[i].to]=;

        if(ma[ed[i].to]==||Dfs(ma[ed[i].to],t)){ma[ed[i].to]=x;return ;}

    }

    return ;

}

bool pd(int t){

    memset(ma,,sizeof(ma));

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

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

            if(ch[i][j]=='.'){

                memset(vis2,,sizeof(vis2));

                if(!Dfs(M1(i,j),t)) return ;

            }

    return ;

}

int main(){

    int t;

    scanf("%d",&t);

    for(int jsjs=;jsjs<=t;jsjs++){

        scanf("%d%d",&x,&y);

        memset(head,,sizeof(head));

        tot=;

        for(int i=;i<=x;i++) for(int j=;j<=y;j++) scanf(" %c",&ch[i][j]);

        for(int i=;i<=x;i++) for(int j=;j<=y;j++) if(ch[i][j]=='.') Bfs(i,j);

        int l=,r=;

        while(l<=r){

            int mid=(l+r)/;

            if(pd(mid)) r=mid-;

            else l=mid+;

        }

        if(l==) printf("impossible\n");

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

    }

    return ;

}

1S

Evacuation，题解

题目：

题意：

分析：