P3191 EVACUATE

· · 题解

不错的网络流题。

首先二分答案 t，考虑 check 里面用网络流。

可以考虑把每一个门都拆开成 t 个时间的门，显然每个时间最多有一人进入门。

建图方式如下：

  1. 源点 S 连向每一个人。
  2. 每个门拆改每个时间的点连向汇点。

预处理出每个人到门的距离，连到这个时间的门。

有一个问题就是可能好多人同时到达同一扇门。

可以把一扇门 x 时间向 x+1 时间连一条 +\infty 的边即可。

因为 n,m\le 20，可以通过。

// Author: Jerry_Jiang
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
    if (a > b)
        return a;
    return b;
}
int min(int a, int b)
{
    if (a < b)
        return a;
    return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10, M = 1e6 + 10;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

namespace MaxFlow
{
    // Here, M needs to be doubled.
    // In this program, int <-> long long
    int head[N], nxt[M], to[M], cnt = 1;
    int lim[M];
    void init()
    {
        memset(head, 0, sizeof(head));
        cnt = 1;
    }
    void addEdge(int u, int v, int w)
    {
        // cerr << u << " " << v << " " << w << endl;
        nxt[++cnt] = head[u], head[u] = cnt, to[cnt] = v, lim[cnt] = w;
        nxt[++cnt] = head[v], head[v] = cnt, to[cnt] = u, lim[cnt] = 0;
    }
    int T, dis[N], cur[N];
    int dfs(int u, int res)
    {
        if (u == T)
            return res;
        int flow = 0;
        for (int i = cur[u]; i && res; i = nxt[i])
        {
            cur[u] = i;
            int v = to[i];
            int c = min(res, lim[i]);
            if (c && dis[v] == dis[u] + 1)
            {
                int k = dfs(v, c);
                flow += k;
                res -= k;
                lim[i] -= k;
                lim[i ^ 1] += k;
            }
        }
        if (!flow)
            dis[u] = -1;
        return flow;
    }
    int maxflow(int s, int t)
    {
        T = t;
        int flow = 0;
        while (1)
        {
            queue<int> q;
            memset(dis, -1, sizeof(dis));
            memcpy(cur, head, sizeof(head));
            dis[s] = 0;
            q.push(s);
            while (!q.empty())
            {
                int u = q.front();
                q.pop();
                for (int i = head[u]; i; i = nxt[i])
                {
                    int v = to[i];
                    if (dis[v] == -1 && lim[i])
                    {
                        dis[v] = dis[u] + 1;
                        q.push(v);
                    }
                }
            }
            if (dis[t] == -1)
                return flow;
            flow += dfs(s, INF);
        }
    }
};

// bool st;
int n, m, dis[410][22][22], cnt = 0;
char s[22][22];
int id[22][22];
queue<pii> q;
// bool en;

void BFS(int sx, int sy)
{
    q.push({sx, sy});
    dis[id[sx][sy]][sx][sy] = 0;
    while (!q.empty())
    {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int tx = x + dx[i], ty = y + dy[i];
            if (tx >= 1 && tx <= n && ty >= 1 && ty <= m && s[tx][ty] != 'X' && dis[id[sx][sy]][tx][ty] > 1e9)
            {
                dis[id[sx][sy]][tx][ty] = dis[id[sx][sy]][x][y] + 1;
                q.push({tx, ty});
            }
        }
    }
}

bool check(int L)
{
    int S = 0, T = 2e5;
    MaxFlow::init();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (s[i][j] == '.')
            {
                MaxFlow::addEdge(S, id[i][j], 1);
                for (int x = 1; x <= n; x++)
                    for (int y = 1; y <= m; y++)
                        if (s[x][y] == 'D' && dis[id[i][j]][x][y] <= L)
                        {
                            MaxFlow::addEdge(id[i][j], id[x][y] + (dis[id[i][j]][x][y] - 1) * 400, 1);
                        }
            }
            else if (s[i][j] == 'D')
            {
                for (int k = 1; k <= L; k++)
                {
                    MaxFlow::addEdge(id[i][j] + (k - 1) * 400, T, 1);
                    if (k < L)
                        MaxFlow::addEdge(id[i][j] + (k - 1) * 400, id[i][j] + k * 400, INF);
                }
            }
        }
    return MaxFlow::maxflow(S, T) == cnt;
}

void solve()
{
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%s", s[i] + 1);
    memset(dis, 0x3f, sizeof(dis));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            id[i][j] = (i - 1) * m + j;
            if (s[i][j] == '.')
            {
                cnt++;
                BFS(i, j);
            }
        }
    int l = 0, r = 400;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    if (!check(l))
        puts("impossible");
    else
        printf("%lld\n", l);
}

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--)
        solve();
    return 0;
}