蟻本 : Evacuation (POJ No.3057)

蟻本 p.206 の Evacuation (POJ No.3057) のノート.

(時刻-ドア, 人) 間の二部グラフの最大マッチング = 全員が脱出するまでの時間 となる.
最大マッチングが全人数に満たない場合は impossible.

ドアの集合を D,人の集合を P とし,各 d_i \in D についてすべての p_i \in P までの最短距離を BFS で求める.
この距離が,p_id_i を使って脱出するときの最短時間となる.
得られた距離をもとにグラフを作成する.

コード
- C++ : https://github.com/1izard/algorithm-training/blob/master/Ant/chapter3/cpp/evacuation.cpp
- Python : https://github.com/1izard/algorithm-training/blob/master/Ant/chapter3/python/evacuation.py

for (int k = dist[dX[i]][dY[i]][pX[j]][pY[j]]; k <= N; ++k) は各時刻について走査.
dist[dX[i]][dY[i]][pX[j]][pY[j]] = 最短時刻で,この時刻以降この人はこのドアから任意の時刻に脱出できるので,脱出までに最も時間がかかった場合の時刻 N までインクリメントして (時刻-ドア,人) 間に辺をつなぎ続ける.

int D = dX.size();
int P = pX.size();
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) {
        add_edge((k - 1) * D + i, N * D + j);
      }
    }
  }
}

add_edge((k - 1) * D + i, N * D + j)(k - 1) * D + iN * D + j を, 例えば 10 進数 23 を 2 * 10 + 3 と基数に基づいて考えるように,ドアの総数 D を基数と捉えると各時刻 t1, t2, t3, ... について各ドアを下の表のような順で頂点としていることがわかる.

f:id:espe0n:20201120002112p:plain

例えば次のような入力の場合,グラフはこんな感じになる.

4 4
XXXX    
D..X    d1 p1 p2
X..D       p3 p4 d2
XXXX

f:id:espe0n:20201120001906p:plain

最後に t1, t2, ..., tN までの時刻の全てのドアと人をマッチングしていく.
早い時刻から可能な限りドアと人をマッチングさせるので,初めてマッチング数が人数 P に等しくなったときが最短時刻になる.

int cnt = 0;
memset(match, -1, sizeof(match));
for (int u = 0; u < N * D; ++u) {
  memset(used, 0, sizeof(used));
  if (dfs(u)) {
    if (++cnt == P) {
      printf("%d\n", u / D + 1);
      return;
    }
  }
}
printf("impossible\n");