![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 22. Потоки в сетях. if (mark[v] — valid) return phi[v];
{ if (mark[v] — valid) return phi[v]; phi[v] = phiR(ST(v)) - st[v]-> costRto(v); mark[v] = valid; return phi[v]; }
Как и раньше, мы наращиваем поток в цикле посредством одного обхода путей с тем, чтобы выявить максимальную величину потока, которую мы можем протолкнуть через их ребра, с последующим вторым обходом обоих этих путей с целью протолкнуть через них поток. РИСУНОК 22.47. ВЫЧИСЛЕНИЕ ПОТЕНЦИАЛОВ С ИСПОЛЬЗОВАНИЕМ РОДИТЕЛЬСКИХ СВЯЗЕЙ Мы начнем вычисления с вершины О, пройдем вдоль пути в корень, установим значение pt[5] равным нулю, а затем, следуя вниз тем же путем, установим вершине 6 такое значение, чтобы pt[6] -pt[5] было равно стоимости ребра 6-5, затем установим значение pt[3] таким, чтобы pt[3] -pt[6] было равным стоимости ребра 3-6 и т.д. (диаграмма слева). Затем мы начинаем с вершины 1 и следуем вдоль родительских связей, пока не столкнемся с вершиной, потенциал которой известен (в данном случае это 6), и следуем вниз по этому пути с тем, чтобы вычислить потенциалы вершин 9 и 1 (диаграмма в центре). Далее, отправляясь от вершины 2, мы можем рассчитать ее потенциал, взяв за основу потенциал ее родителя (диаграмма справа). Когда мы отправимся из вершины 3, мы видим, что ее потенциал уже известен, и т.д. В рассматриваемом примере, когда мы проверяем каждую вершину после вершины 1, мы узнаем, что ее потенциал уже подсчитан, либо мы можем вычислить его, взяв за основу потенциал ее родителя. Мы никогда не проходим по одному и тому же ребру дважды, независимо от того, какую структуру имеет дерево, поэтому суммарное время этих вычислений линейно. Часть 5. Алгоритмы на графах
Программа 22.11. Наращивание потока вдоль цикла_______________________________ Чтобы найти наименьшего общего предшественника двух вершин, мы, отправляясь из них вверх по дереву, синхронно помечаем узлы. LCA-предшественник есть корень в тех случаях, когда он является единственным обнаруженным помеченным узлом. В противном случае LCA-предшественник есть первый обнаруженный помеченный узел, не являющийся корнем. Чтобы нарастить поток, мы используем функцию, аналогичную используемой в программе 22.3; она сохраняет пути в векторе st и возвращает ребро, которое было опорожнено или заполнено в процессе наращивания (см. рассуждения по тексту).
|