POJ 3367 Evacuation - simezi

写経してただけなのにWAが出続けてイミフだった。
自分の2部グラフの最大マッチングがバグっているのだろうか。

XxYマスの部屋がある。
それぞれのマスは、床'.',壁'X',ドア'D'のいずれかであり、
ドアは部屋の内部にはない。

最初それぞれの床には一人の人がいて、全員がドアから部屋を脱出したい。
人は、1秒に上下左右の好きなマスに動くことができるが、壁には入ることはできない。
一つのドアは1秒に一人しか通ることができない。

全員が避難するまでにかかる時間の最小値を求めよ。

X,Y≦12

蟻本の解説の通り。
それぞれの人間を左側の頂点に、1秒からn秒までのドアを右側にするような二部グラフを作る。
その時間でドアに辿り着けるとき、人間の頂点とドアの頂点に辺を貼る。

1秒のドアから順に最大マッチングを行っていき、全員がマッチングできたときが、
全員が脱出するのにかかる最短の時間である。

写経なので略。