最大流問題 5 (paizaランク B 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

前回は、最大流問題を解く下準備として、逆辺を利用したフローの流し方を学びました。では、それを繰り返して、最大流を求めてみましょう。
ちなみに、このアルゴリズムは Ford-Fulkerson 法と呼ばれていて、最大流問題の解法の中で最も基本的なものになります。

辺に容量の制約がある n 頂点 m 辺のグラフが与えられます。各頂点には 1 から n までの番号がついており、各辺は頂点 a_i から頂点 b_i へ向かうもので、容量が c_i になっています。(1 ≦ i ≦ m)
前回使用したコードを利用し、s から t へのパス上に、フローが流れなくなるまで繰り返し流して最大流を求めてください。

入力される値

n m s t
a_1 b_1 c_1
a_2 b_2 c_2
...
a_m b_m c_m

・ 1 行目に、グラフの頂点数を表す整数 n, グラフの辺数を表す整数 m, フローの始点、終点の頂点の番号を表す整数 s, t が半角スペース区切りで与えられます。
・続く m 行では、各辺の情報を表す整数 a_i, b_i, c_i が半角スペース区切りで与えられます。(1 ≦ i ≦ m) a_i, b_i は、辺の始点、終点の頂点の番号を表します。c_i は、i 番目の辺に流すことのできる最大の流量を表します。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 1 行に、フローの流量を表す整数を出力してください。
また、末尾に改行を入れ、余計な文字を含んではいけません。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・入力はすべて整数
・ 2 ≦ n ≦ 100 = 10^2
・ 1 ≦ m ≦ 10,000 = 10^4
・ 1 ≦ s, t, a_i, b_i ≦ n
・ 1 ≦ c_i ≦ 100 = 10^2
・ s ≠ t, a_i ≠ b_i
・ (a_i, b_i) ≠ (a_j, b_j) (i ≠ j)

入力例1: 4 5 1 4
1 2 20
1 3 15
2 3 10
2 4 20
3 4 15

出力例1: 35

問題一覧へ戻る