きままにものづくり

日々の気付いたことなんかを書いてます。

SRM632Div1Medium

問題

N個のノードとM個の無向エッジが与えられる。各エッジには 3^iの容量が与えられる。ノード0からN-1までの最大流を求めよ。ただし、答えは1000000007でmodをとる。

解法

Ford-Fulkersonは計算量的にも、エッジの最大容量的にも使用することができない。Ford-Fulkersonの計算量は最大流に比例する。また、エッジの最大容量は 3^{2000}となるため、通常の方法では容量を保存できない。
0からN-1までのルートがなくなるまでエッジを除去していき答えを求める。最初に全てのエッジを張り、その後ルートがなくなるまで除去する方法だと、各エッジを取り除く際のコストが計算出来ない。
初めは、何もエッジをはらない状態からスタートする。iが大きい順にエッジを追加していき、0からN-1までのパスが出来た状態を考える。この時の最大流は3^iとなる。なぜなら、3^iより小さい容量を持つエッジが存在しないからである。また、i+1の状態では0からN-1までのパスは存在しなかったので、iは必ず通ることになる。これを最後まで行うことで答えが求まる。

計算量

パス探索: O(N)
エッジ追加 O(M)
全体: O(NM)

コード

広告を非表示にする