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

最大流問題を解くためには、フローをできるだけ流す必要があります。その準備として、s から t へのパスを 1 つ選び、そのパス上の辺にできるだけ大きい流量のフローを流してみましょう。

辺に容量の制約がある n 頂点 m 辺のグラフが与えられます。各頂点には 1 から n までの番号がついており、各辺は頂点 a_i から頂点 b_i へ向かうもので、容量が c_i になっています。(1 ≦ i ≦ m)
以下のアルゴリズムにしたがって s から t へのパスを 1 つ選び、できるだけ大きい流量のフローを流してください。
流したフローの流量と、最後に残ったグラフの各辺の容量 (コード中の隣接行列 capacity) をすべて出力してください。存在しない辺については 0 を出力してください。

以下のアルゴリズムと同じ訪問順でない場合、正答が得られない可能性があるため注意してください。

s から t へのパス上にフローを流すアルゴリズム (擬似コード):

・ 以下の関数を定義する。

// 頂点 v から t' まで最大で流量 f のフローを流し、流れたフローの流量を返す関数
push_flow(v, t', f)
    // v が t' であれば、フローが流れたことになる
    if v == t'
        return f
    
    // v を訪問済みにする
    visited[v] = true

    // 容量の隣接行列 capacity を順に見ていく
    for u = 1 to n
        // u が未訪問で、辺の容量が残っている場合
        if visited[u] == false && capacity[v][u] > 0
            // 容量を f と capacity[v][u] の小さいほうにしてフローを流す
            f' = push_flow(u, t', min(f, capacity[v][u]))
            // もしフローが流れた場合
            if f' > 0
                // 容量を減らす
                capacity[v][u] -= f'
                // フローが流れた量を返す
                return f'

    // この頂点から t' までフローを流せなかった場合は 0 を返す
    return 0

・ push_flow(s, t, 100) を呼び出す。(100 は流量の上限)