Int lca (int v, int w)

{ mark[v] = ++valid; mark[w] = valid; while (v! = w) {

if (v! = t) v = ST(v);

if (v! = t & & mark[v] == valid) return v; mark[v] = valid; if (w! = t) w = ST(w);

if (w! = t & & mark[w] == valid) return w; mark[w] = valid;

>

return v; } Edge *augment(Edge *x)

{ int v == x-> v(), w = x-> w(); int r == lca(v, w); int d = x-> capRto (w);

for (int u = w; u! = r; u = ST(u)) if (st[u]-> capRto(ST(u)) < d)

d = st[u]-> capRto(ST(u)); for (int u = v; u! = r; u = ST(u)) if (st[u]-> capRto(u) < d)

d =st[u]-> capRto(u); x-> addflowRto (w, d); Edge* e = x; for (int u = w; u! = r; u = ST(u)) { st[u]-> addflowRto(ST(u), d);

if (st[u]-> capRto(ST(u)) == 0) e = st[u]; } for (int u = v; u! = r; u = ST(u)) { st[u]-> addflowRto(u, d);

if (st[uJ-> capRto(u) ==0) e = st[u]; } return e; }

Реализация в программе 22.11 использует простую технологию, чтобы избежать затрат на инициализацию всех меток, которую нужно выполнять каждый раз при вызове про­граммы. Мы храним эти метки как глобальные переменные, инициализированные нуля-

Глава 22. Потоки в сетях

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

Наша третья задача, требующая манипулирования элементами дерева, есть подстанов­ка вместо ребра u-v другого ребра в цикле, который это другое ребро образует с древес­ными ребрами. В программе 22.12 реализована функция, выполняющая эту задачу на де­реве, представленном в виде родительских связей. И снова LCA-предшественник вершин и и v играет важную роль, поскольку удаляемое ребро лежит либо на пути из и в LCA, либо на пути из v в LCA. Удаление ребра приводит к отсоединению от дерева всех его потомков, однако мы можем скомпенсировать нанесенный ущерб, меняя направление связи между ребром u-v и удаленным ребром на обратные, как показано на рис. 22.48.

РИСУНОК 22.48. ПОДСТАНОВКА ОСТОВНОГО ДЕРЕВО

Этот пример служит иллюстрацией базовой операции манипулирования деревом в сетевом симплекс­ном алгоритме для случая представления графа в виде родительских связей. На диаграмме слева изображено демонстрационное дерево, в котором все связи направлены вверх, как показывает структура ST родительских связей. (В рассматриваемой нами программе функция ST вычисляет родителя заданной вершины по указателю, хранящемуся в векторе st, индексированном вершинами.) Добавление ребра 1-2 приводит к образованию цикла, в который входят пути из вершин 1 и 2, ведущие к из LCA-предшественнику, в роли которого выступает вершина 11. Если мы удалим одно из этих ребер, скажем, 0-3, структура сохранит древовидный характер. Чтобы внести изменения в массив родительских связей, отражающие эти изменения, мы меняем направления всех связей из 2 в 3 (диаграмма в центре). Дерево справа есть то же дерево, в котором позиции узлов изменены таким образом, что все связи направлены вверх в соответствии со значениями массива родительских связей, представляющего рассматриваемое дерево (диаграмма справа).