蟻本のFord-Fulkerson法のedge構造体のrevについて
蟻本p190のコードのedge構造体はto, cap. revと3つの値を持つが,revの意味がどうしてもわからかったのでメモ.
add_edge関数にて,
G[from].push_back((edge){to, cap, G[to].size()});
とある.これは,最後にtoのサイズを足すことで,逆辺がどこに保持されているかをあとで逆算するための値.
続く行も同じ.サイズを1小さくしてるのは,前行のpush_backにてサイズが1個増えてしまってるから.逆辺は始めキャパ0なのでfrom, 0, ~~~size()-1
のような初期化になってる
多分,この値が無くても逆辺用の別の2次元vectorを持てば実装できる.気がする.