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

前回は、s から t へのパス上に、フローが流れなくなるまで繰り返し流しましたが、この方法だと最大まで流れない場合があります。そこで鍵となるのが逆辺です。

基本的な考え方は、フローが流れている辺には逆向きにフローを流し戻すことができる、ということです。

たとえば、辺 (a, b) の容量を 3 として、この辺に流量 3 のフローが流れているとしましょう。
このとき、この状態からさらに辺 (b, a) に、つまり逆向きに流量 3 のフローを流すことで、相殺して最初の何も流れていない状態に戻すことができます。
つまり、ある辺にフローを流すと、その辺の容量は流した分だけ減り、逆向きの辺の容量が流した分だけ増えるということを意味します。

この性質を考慮した上で繰り返しフローを流すことで、最大流を正しく求めることができます。

では、実際に逆辺を使ってフローを流す準備をしていきましょう。

辺に容量の制約がある 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'
                // ** 逆辺の容量を増やす **
                capacity[u][v] += f'
                // フローが流れた量を返す
                return f'

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

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