Dinic with Dynamic Tree

個人的メモ

Dinic 法では各頂点について現在見ている辺の添字 $iter$ を持つことで 1 回のフェーズを $\O (mn)$ 時間で計算することが可能であった. これはアルゴリズムが $n$ ステップ進めば "増加道が見つかる" もしくは "現在進んでいる方向には増加道が存在しない" のどちらか一方が起こり, 両方の場合についてある頂点の $iter$ が少なくとも 1 つ進むからである. 前者の場合はフローを流すことで増加道上の少なくとも 1 つの辺の容量が 0 となりその辺から $iter$ が 1 つ進み, 後者の場合も現在たどったパスの最後の辺について $iter$ が 1 つ進む. 全頂点について $iter$ の総増加回数は合計 $\O (m)$ であるのでこれで $\O (mn)$ が保証できるといった寸法である.
ここでは動的木を用いることでならし $\O (\log n)$ 時間で $iter$ が 1 ステップ進むようにしている. 具体的に管理する森は根を $t$ とし, その辺集合は各頂点について現在見ている辺(添字 $iter$ に対応する辺) からなる((注) 自分の実装では逆向きに見ている). 新たに辺を link したとき, sink $t$ と連結になれば増加道が存在し, $s$ と $t$ を結ぶパス上の辺の最小容量をパス上の辺すべてから減じる(ならし計算量 $\O (\log n)$ で実現可能). もし連結とならなければ, パスの $s$ とは異なるほうの端の頂点について $iter$ が 1 つ進むことになる(ならし計算量 $\O( \log n)$ で実現可能).
よって結局 $\O( mn \log n)$ 時間で最大流を求めることが可能になる.