Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2008-10-21

WorkersOnPlane (SRM422 DIV1 Hard)

| 01:28 | WorkersOnPlane (SRM422 DIV1 Hard) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - WorkersOnPlane (SRM422 DIV1 Hard) - TopCoder煮ブログ

しばらく考えて分からなかったので全体一位の人(neal_wuさん)のコードをみた。まず、ある W から到達できる G と S を列挙している。この情報を元に、次のような最大フロー問題を考える。

            /-S\
  /G---W---W--S-\
S--G--/     \-S--D
  \G---W---W--S-/

どの組み合わせを選ぶかは、最大で何本のフローを流せるかに帰着する。

問題を解くには Edmonds-Karp 法を使う。最短路を求めるところは、ちょっと工夫した深さ優先探索で実施している。(ゴールから順番に枝を確認していけば、自動的にそれは最短路になる)

一点、逆順に流れを記録している理由がよく分からん…。たしかに、これをしないと System Test で落ちている。

→ 試してみた。逆流する余地を残している。逆流して流れる場合は、イメージ的には以前の道を付け替えるような感じ。Edmonds-Karp 法での流量分減らす処理に対応している。

最大フロー問題と Edmonds-Karp 法が少し分かった気がする。