Глава 22. Потоки в сетях. if (mark[v] — valid) return phi[v];

int phiR(int v)

{

if (mark[v] — valid) return phi[v];

phi[v] = phiR(ST(v)) - st[v]-> costRto(v);

mark[v] = valid;

return phi[v]; }

Пусть даны две вершины, их LCA-предшественник (least common ancestor - наимень­ший общий предшественник) есть корень минимального поддерева, которое содержит обе эти вершины. Цикл, который мы строим за счет добавления ребра, соединяющего две вершины, состоит из этого ребра плюс ребра двух путей, ведущие из двух этих узлов к их LCA-предшественнику. Этот цикл, образованный благодаря добавлению ребра v-w, проходит через v-w в w, затем вверх по дереву к LCA-предшественнику вершины v и w (его имя, скажем, г), затем вниз по дереву в v, таким образом, мы должны на этих двух путях рассматривать ребра в их противоположной ориентации. Программа 22.11 представ­ляет собой реализацию этой идеи в виде функции, которая наращивает поток в заданном цикле и возвращает ребро, заполненное или опорожненное в процессе этого наращива­ния.

Как и раньше, мы наращиваем поток в цикле посредством одного обхода путей с тем, чтобы выявить максимальную величину потока, которую мы можем протолкнуть через их ребра, с последующим вторым обходом обоих этих путей с целью протолкнуть через них поток.

РИСУНОК 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. Алгоритмы на графах