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