POJ 3057-Evacuation（最短路+二分图匹配）

痛定思痛。 2022-09-24 06:19 149阅读 0赞

# Evacuation #

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 2272</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 573</td> 
  </tr> 
 </tbody> 
</table>

Description

Fires can be disastrous, especially when a fire breaks out in a room that is completely filled with people. Rooms usually have a couple of exits and emergency exits, but with everyone rushing out at the same time, it may take a while for everyone to escape.  
  
You are given the floorplan of a room and must find out how much time it will take for everyone to get out. Rooms consist of obstacles and walls, which are represented on the map by an 'X', empty squares, represented by a '.' and exit doors, which are represented by a 'D'. The boundary of the room consists only of doors and walls, and there are no doors inside the room. The interior of the room contains at least one empty square.  
  
Initially, there is one person on every empty square in the room and these persons should move to a door to exit. They can move one square per second to the North, South, East or West. While evacuating, multiple persons can be on a single square. The doors are narrow, however, and only one person can leave through a door per second.  
  
What is the minimal time necessary to evacuate everybody? A person is evacuated at the moment he or she enters a door square.

Input

The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:  
One line with two integers Y and X, separated by a single space, satisfying 3 <= Y, X <= 12: the size of the room  
Y lines with X characters, each character being either 'X', '.', or 'D': a valid description of a room

Output

For every test case in the input, the output should contain a single line with the minimal evacuation time in seconds, if evacuation is possible, or "impossible", if it is not.

Sample Input

3
    5 5
    XXDXX
    X...X
    D...X
    X...D
    XXXXX
    5 12
    XXXXXXXXXXXX
    X..........D
    X.XXXXXXXXXX
    X..........X
    XXXXXXXXXXXX
    5 5
    XDXXX
    X.X.D
    XX.XX
    D.X.X
    XXXDX

Sample Output

3
    21
    impossible

Source

[The 2006 Benelux Algorithm Programming Contest][]

## 题目意思： ##

墙壁“X”，空区域（都是人）“.”， 门“D”。

人向门移动通过时视为逃脱，门每秒能出去一个人，人可以上下左右移动，墙阻止移动。

求最优移动方案下，最后一个人逃脱的最短时间。如果有人无法安全逃脱（比如被墙围困住），则输出“impossible”。

## 解题思路： ##

看不太懂…我还是超级弱…勉强能照着书敲出来AC代码…

[思路From：][From]

由于空间中每个只能有一人，所以直接bfs求得的值不是最终值，采用二分图匹配；

先bfs处理处每个人距离每一扇门的最短距离，并分别保存在单独一扇门对应的集合中；

若一个人能到达一扇门，则将该人与之后各时刻该门的建边；

求二分图的最大匹配，看是否能将所有人匹配完；从小时刻向大时刻枚举门，则为最优解。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<vector>
    #include<queue>
    #include<algorithm>
    using namespace std;
    
    int V,X,Y;
    char field[13][13];
    int dir[4][2]= {
        {1,0},{-1,0},{0,1},{0,-1}};
    vector<int> G[50010];
    vector<int> dx,dy; //门的坐标
    vector<int> px,py; //人的坐标
    int link[50005];
    int dist[13][13][13][13];//最近距离
    bool vis[50005];
    
    void adde_dge(int u,int v)
    {
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    bool dfs(int v)
    {
        vis[v]=true;
        for(int i=0; i<G[v].size(); i++)
        {
            int u=G[v][i];
            if(link[u]==-1||!vis[link[u]]&&dfs(link[u]))
            {
                link[v]=u;
                link[u]=v;
                return true;
            }
        }
        return false;
    }
    
    void bfs(int x,int y,int d[13][13])//计算最短距离
    {
        queue<int> qx,qy;
        d[x][y]=0;
        qx.push(x);
        qy.push(y);
        while(!qx.empty())
        {
            x=qx.front();
            qx.pop();
            y=qy.front();
            qy.pop();
            for(int k=0; k<4; k++)
            {
                int x2=x+dir[k][0];
                int y2=y+dir[k][1];
                if(0<=x2&&x2<X&&0<=y2&&y2<Y&&field[x2][y2]=='.'&&d[x2][y2]<0)
                {
                    d[x2][y2]=d[x][y]+1;
                    qx.push(x2);
                    qy.push(y2);
                }
            }
        }
    }
    
    void solve()
    {
        int n=X*Y;
        dx.clear();
        dy.clear();
        px.clear();
        py.clear();
        memset(dist,-1,sizeof(dist));
        for(int x=0; x<X; x++)//计算到各个门的最短距离
            for(int y=0; y<Y; y++)
            {
                if(field[x][y]=='D')
                {
                    dx.push_back(x);
                    dy.push_back(y);
                    bfs(x,y,dist[x][y]); //每个人能到该点的最小距离
                }
                else if(field[x][y]=='.')  //if中的==要注意
                {
                    px.push_back(x);
                    py.push_back(y);
                }
            }
        //建图
        int d=dx.size(),p=px.size();
        V=X*Y*d+p;
        for(int v=0; v<V; ++v) G[v].clear();
        for(int i=0; i<d; i++)
            for(int j=0; j<p; j++)
                if(dist[dx[i]][dy[i]][px[j]][py[j]]>=0)  //若该人能到达该门
                    for(int k=dist[dx[i]][dy[i]][px[j]][py[j]]; k<=n; k++)
                        adde_dge((k-1)*d+i,n*d+j); //该人与不同时间的该门建边
        if(p==0)
        {
            cout<<"0"<<endl;
            return;
        }
        int res=0;
        memset(link,-1,sizeof(link));
        for(int v=0; v<n*d; v++) //枚举门的集合
        {
            memset(vis,0,sizeof(vis));
            if(dfs(v))
                if(++res==p)  //若所有人能逃出
                {
                   cout<<(v/d+1)<<endl;;
                    return;
                }
        }
        cout<<"impossible"<<endl;
    }
    
    int main()
    {
        int i,j,k,t;
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin>>t;
        while(t--)
        {
            cin>>X>>Y;
            for(i=0; i<X; i++)
                cin>>field[i];
            solve();
        }
    }

[The 2006 Benelux Algorithm Programming Contest]: http://poj.org/searchproblem?field=source&key=The+2006+Benelux+Algorithm+Programming+Contest
[From]: http://www.cnblogs.com/dominatingdashuzhilin/p/4734876.html