POJ 3057 Evacuation（二分匹配）

分析：

这是一个时间和门的二元组(t,d)和人p匹配的问题，当我们固定d₀时，(t,d₀)匹配的人数和t具有单调性。

t增加看成是多增加了边就行了，所以bfs处理出p到每个d的最短时间，然后把(t,d)和p连边，按t从小到大

枚举点增广就好了。无解的情况只有一种，某个人无论如何都无法出去。

/*********************************************************
*      --Sakura hirahira mai orite ochite--              *
*   author AbyssalFish                                   *
**********************************************************/
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
using namespace std;

typedef long long ll;

const int XY = 12, MAX_D = 44, MAX_P = 100;//..MAX_T
char maz[XY][XY+1];

const int maxv = MAX_D*MAX_P, maxe = maxv*MAX_P;
int hd[maxv],to[maxe],nx[maxe],ec;
#define eachEage int i = hd[u]; ~i; i = nx[i]
void add(int u,int v)
{
    nx[ec] = hd[u];
    to[ec] = v;
    hd[u] = ec++;
}

#define PB push_back
#define resv(x,n) x.reserve(n);
#define PS push
vector<int> pX, pY, dX, dY;

const int dx[] = {0,0,-1,1}, dy[] = {1,-1,0,0};

int dist[XY][XY][XY][XY];
int X,Y;


void bfs(int x,int y)
{
    int (* const d)[XY] = dist[x][y];
    memset(d,0xff,sizeof(dist[x][y]));

    queue<int> qx, qy;
    d[x][y] = 0;
    qx.PS(x); qy.PS(y);
    while(qx.size()){
        x = qx.front(); qx.pop();
        y = qy.front(); qy.pop();
        for(int k = 4; k--;){
            int nx = x+dx[k], ny = y+dy[k];
            if(0<=nx && nx<X && 0<=ny && ny<Y && maz[nx][ny] == '.' && d[nx][ny]<0){
                d[nx][ny] = d[x][y]+1;
                qx.PS(nx); qy.PS(ny);
            }
        }
    }
}

int link[MAX_P];
int vis[maxv], clk;

bool aug(int u)
{
    vis[u] = clk;
    for(eachEage){
        int v = to[i], w = link[v];
        if(w<0 || (vis[w] != clk && aug(w))){
            link[v] = u;
            return true;
        }
    }
    return false;
}

//#define LOCAL
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    resv(pX,MAX_P) resv(pX,MAX_P) resv(dX,MAX_D) resv(dY,MAX_D)
    int T; cin>>T;
    while(T--){
        scanf("%d%d",&X,&Y);
        pX.clear(); pY.clear();
        dX.clear(); dY.clear();
        for(int i = 0; i < X; i++){
            scanf("%s", maz[i]);
            for(int j = 0; j < Y; j++){
                if(maz[i][j] == 'D'){
                    dX.PB(i); dY.PB(j);
                }
                else if(maz[i][j] == '.'){
                    pX.PB(i); pY.PB(j);
                }
            }
        }
        int d = dX.size(), p = pX.size();
        if(p == 0){ puts("0"); continue; }
        for(int i = 0; i < d; i++){
            bfs(dX[i],dY[i]);
        }
        int n = (X-2)*(Y-2);
        bool fail = false;
        memset(hd,0xff,sizeof(int)*n*d); ec = 0;
        for(int i = 0; i < p; i++){
            bool escape = false;
            for(int j = 0; j < d; j++){
                if(dist[dX[j]][dY[j]][pX[i]][pY[i]] > 0){
                    if(!escape) escape = true;
                    for(int k = dist[dX[j]][dY[j]][pX[i]][pY[i]]-1; k < n; k++){
                        add(k*d+j, i);
                    }
                }
            }
            if(!escape){
                fail = true; break;
            }
        }
        if(fail){ puts("impossible"); continue; }
        memset(link,-1,sizeof(int)*p);
        int cnt = 0, ans;
        for(int i = 0; i < n*d; i++){
            clk++;
            if(aug(i) && ++cnt == p) {
                ans = i/d+1;
            }
        }
        printf("%d
", ans);
    }
    return 0;
}