1886_프리즌 브레이크/Evacuation

나는 이분탐색 + 유량으로 풀었는데, 사실 가중치가 1이라서 그냥 이분매칭이다.

주차장 문제랑 좀비 아포칼립스 문제를 짬뽕시킨 느낌이었다.

아마 이분 매칭이면서 시간에 따른 정점 분리도 해서 그런 것 같다.

탈출구를 시간에 따라 정점 분리를 해줬다. 

1초일때의 탈출구, 2초일때의 탈출구... 그리고 각각 1의 가중치로 sink와 연결

빈칸인애들은 가중치 1로 source와 연결해준다. (이 때 가중치 = 유량은 사람을 뜻함)

빈칸이나 벽인 애들은 굳이 해 줄 필요가 없다.

그리고 빈칸에서부터 탈출구까지의 거리를 구했다.

이 때 나는 모든 빈칸을 출발지로 하고 bfs를 돌렸는데, 플로이드 워셜로 하신 분도 있고

아니면 탈출구의 갯수가 (일반적으로) 더 적으니까 탈출구를 기준으로 bfs 돌려도 될거같다. 

정점개수가 작아서 어떻게 하든 큰 차이는 없는 거 같다.

그래서 각각의 모든 빈칸 -> 모든 탈출구에 1의 간선을 연결해주었다.

다른 칸은 신경 쓸 필요가 없는 이유는, 탈출하는 중에는 빈칸에 몇명이 있든 상관없다고 했으므로

그냥 자유롭게 움직인다 = 혼자있는 것처럼 생각한다 해서 그냥 바로 탈출구랑 연결하면 된다.

그 거리를 유량의 엣지에 같이 저장해주고, 이분탐색을 하면서 MID값보다 작거나 같은 edge만 유효하게 해주었다.

그래서 유량을 MID값마다 돌리면서 인구랑 같은 유량이 나오면 y를 줄이고 안나오면 x를 늘린다.

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <string.h>
using namespace std;
#define MAX 50001
#define TIME 100
struct Edge {
    int v, cap, rev, val;
    Edge() {}
    Edge(int v, int cap, int rev, int val = 0) : v(v), cap(cap), rev(rev) , val(val) {}
};
// S : Source , T : Sink
int N, M, S = 0, T, work[MAX], level[MAX];
vector<vector<Edge>> adj, ori;
char maap[15][15];
int idx[15][15], dcnt, emcnt, a[8] = { -1, 1, 0, 0, 0, 0, -1, 1 };
int visit[15][15];
vector<pair<int, int>> d, em;
 
void addEdge(int u, int v, int cap, int val = 0) {
    adj[u].emplace_back(v, cap, (int)adj[v].size(), val);
    adj[v].emplace_back(u, 0, (int)adj[u].size() - 1, val);
}
 
void addoriEdge(int u, int v, int cap, int val = 0) {
    ori[u].emplace_back(v, cap, (int)ori[v].size(), val);
    ori[v].emplace_back(u, 0, (int)ori[u].size() - 1, val);
}
 
bool bfs(int mid) {
    memset(level, -1, sizeof(level));
    queue<int> q;
    q.push(S); level[S] = 0;
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (int i = 0; i < adj[cur].size(); ++i) {
            int next = adj[cur][i].v;
            int cap = adj[cur][i].cap;
            int val = adj[cur][i].val;
            if (cap > 0 && level[next] == -1 && val <= mid) {
                level[next] = level[cur] + 1;
                q.push(next);
            }
        }
    }
 
    return level[T] != -1;
}
 
int dfs(int cur, int flow) {
    if (cur == T) return flow;
    for (int &i = work[cur]; i < adj[cur].size(); ++i) {
        int next = adj[cur][i].v;
        int cap = adj[cur][i].cap;
        int rev = adj[cur][i].rev;
        if (cap > 0 && level[next] == level[cur] + 1) {
            int cf = dfs(next, min(flow, cap));
            if (cf > 0) {
                adj[cur][i].cap -= cf;
                adj[next][rev].cap += cf;
                return cf;
            }
        }
    }
 
    return 0;
}
 
int solve(int mid) {
    int totalflow = 0;
 
    while (bfs(mid)) {
        memset(work, 0, sizeof(work));
        while (1) {
            int flow = dfs(S, 1e9);
            if (!flow) break;
            totalflow += flow;
        }
    }
 
    return totalflow;
}
 
void bfs2() {
    queue<pair<int, int>> q;
    
    for (auto curr : em) {
        memset(visit, 0, sizeof(visit));
        q.push({ curr.first, curr.second });
        visit[curr.first][curr.second] = 1;
        int curidx = idx[curr.first][curr.second];
        while (!q.empty()) {
            int r = q.front().first;
            int c = q.front().second; q.pop();
            
            for (int i = 0; i < 4; ++i) {
                int nr = r + a[i], nc = c + a[i + 4];
                if (nr < 0 || nc < 0 || nr >= N || nc >= M || visit[nr][nc] ||
                    !idx[nr][nc]) continue;
                
                visit[nr][nc] = visit[r][c] + 1;
                if (maap[nr][nc] == '.') q.push({ nr, nc });
            }
        }
 
        for (auto dd : d) {
            if (visit[dd.first][dd.second] == 0) continue;
            int ddidx = (idx[dd.first][dd.second] - 1) * TIME + emcnt;
            for (int i = visit[dd.first][dd.second] - 1; i <= TIME; ++i) {
                addoriEdge(idx[curr.first][curr.second], ddidx + i, 1, i);
            }
        }
    }
 
    for (auto e : em) {
        addoriEdge(S, idx[e.first][e.second], 1);
    }
 
    for (auto dd : d) {
        for (int i = 1; i <= TIME; ++i) {
            addoriEdge((idx[dd.first][dd.second] - 1) * TIME + i + emcnt, T, 1, i);
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    cin >> N >> M;
 
    for (int i = 0; i < N; ++i) {
        cin >> maap[i];
        for (int j = 0; j < M; ++j) {
            if (maap[i][j] == '.') {
                idx[i][j] = ++emcnt;
                em.push_back({ i, j });
            }
            else if (maap[i][j] == 'D') {
                idx[i][j] = ++dcnt;
                d.push_back({ i, j });
            }
        }
    }
 
    
 
    S = 0, T = dcnt * TIME + emcnt + 1;
    ori.resize(dcnt * TIME + emcnt + 5);
 
    bfs2();
 
 
    int x = 1, y = TIME, mid = 0, res = -1;
    while(x <= y){
        adj = ori;
        mid = (x + y) >> 1;
        if (solve(mid) == emcnt) {
            res = mid;
            y = mid - 1;
        }
        else x = mid + 1;
    }
 
    if (res != -1) cout << res;
    else cout << "impossible";
}