イナズマの日記

こんにちは。

蟻本の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を持てば実装できる.気がする.