![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
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. Потоки в сетях
Наша третья задача, требующая манипулирования элементами дерева, есть подстановка вместо ребра 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 (диаграмма в центре). Дерево справа есть то же дерево, в котором позиции узлов изменены таким образом, что все связи направлены вверх в соответствии со значениями массива родительских связей, представляющего рассматриваемое дерево (диаграмма справа).
|