CODE FESTIVAL 2014 上海オープンコンテスト D : Maze

クソ雑魚なので参加してません。

オンライン参加です。

問題↓


D: Maze - code festival 2014 上海(オープンコンテスト) | AtCoder

問題概要

  • 迷路があります。
  • ゴール2種類あります。(A,B)
  • スタートからゴールへ行く道のりは必ず最短でなければいけません。
  • 各ゴールへ行く時の道筋が被ってはいけません。
  • スタートから各ゴールへの経路を出力して下さい。
    (output は 問題を見た方が分かりやすいです。)

解法

  1. 最初に、bfsでスタートからゴールへの最短経路を求めます。
  2. 次にスタートから流量2の最小費用流を流します。
  3. 最小費用流 が 各ゴールへの最短経路の和 と等しければ 4 へ、異なれば "NA"
  4. 最小費用流の経路復元をしてdfsでゴールまでの経路を書き換えます。
  • 最小費用流のグラフを作るときに、各マスについて受け取るノードと配るノードに分けないと上手くいかないので注意。
    (同じノードを通ってはいけないので ( 受け取るノード -> 配るノード , cap=1, cost = 0 ) を張らなければならない)
  • フローの経路復元は cap の値が減っているかどうかを見ればよい。
    今回はcap が 1 なので(受け取るノード -> 配るノード の cap = 0) になっているようなマスを仮に'x'と置く。
  • dfs は 本当に愚直に行えばOK。x を 辿って 各ゴールに最短でたどり着けば良い。
ソースコード

感想

最初に送ったコードがよく分からないバグでTLEしててDFSにいらん工夫を加えまくった結果バグに悩まされた。

結局愚直にガリガリDFS書いたらに通ってしまった。オーダー的に間に合うのよく分からんなぁ(分岐多そう)