algorithm - 改善された Dinic のアルゴリズムのための動的ツリー データ構造

Question

Dinic のアルゴリズムを動的ツリーに適用したい。しかし、ソースはほとんど見つかりません。特に動的ツリーについて。詳細な説明が記載された適切なソースや、動的ツリーを使用する簡単なソース コードがあれば素晴らしいと思います。

そのようなものに出くわした人はいますか？前もって感謝します

Answer 1

改善の基本的な考え方は、Dinic のアルゴリズムで時期尚早の悲観化を回避することです。プリフロー/プッシュ アルゴリズムとは対照的に、Dinic のアルゴリズムは残差フロー グラフ内のパスを検索します。このようなフローに対処すると、新しい検索を開始する代わりに、変更されたアルゴリズムが以前の検索で見つかったパスを処理します。

データ構造自体の実装を含む、これに関する非常に読みやすい紹介をここで見つけることができます。詳しい講義はこちら。最後に、A Data Structure for Dynamic Trees (Sleator と Tarjan による)は、データ構造自体の実装に焦点を当てたオリジナルの論文です。