Динамическая структура данных дерева для улучшенного алгоритма Dinic

Question

Я хочу применить алгоритм Dinic с динамическим деревом. Но я нахожу очень мало источников. особенно о динамическом дереве. Было бы здорово, если бы был хороший источник с подробными объяснениями или несколькими простыми исходными кодами, в которых используется динамическое дерево.

Любое встречается с чем-то подобным? Заранее спасибо

Answer 1

Основная идея улучшения - избежать преждевременной пессимизации в алгоритме Динича. В отличие от алгоритмов предварительного потока/толчка алгоритм Dinic ищет пути в графе остаточного потока. Как только такой поток адресован, вместо того, чтобы начинать новый поиск, модифицированный алгоритм имеет дело с путями, найденными в предыдущем поиске.

here очень понятное введение для этого, включая реализацию самой структуры данных. here - более подробная лекция. Наконец, A Data Structure for Dynamic Trees (by Sleator and Tarjan) - это оригинальная работа, посвященная реализации самой структуры данных.