![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 22. Потоки в сетях. Свойство 22.22.Задача о допустимом потоке минимальной стоимости и задача о максимальном потоке с минимальной стоимостью эквивалентны.
Доказательство: Непосредственно следует из соответствия, использованного при доказательстве свойства 22.18 (см. также упражнение 22.76). ■ Как следствие этой эквивалентности и в силу того, что задача о допустимом потоке с минимальной стоимостью непосредственно моделирует задачи о распределении товаров и многие другие приложения, мы употребляем термин поток минимальной стоимости (minicost flow) для обозначения обеих задач в контексте, в котором мы будем ссылаться на любую из них. Сведения к другим задачам мы рассмотрим в разделе 22.7. Чтобы иметь возможность использовать стоимости ребер в транспортных сетях, введем целочисленный элемент данных pcost в класс EDGE из раздела 22.1 и функцию-элемент cost(), возвращающую значение стоимости клиенту. Программа 22.8 представляет собой клиентскую функцию, которая вычисляет стоимость потока в графе, в котором построены указатели на такие ребра. Как и в случаях, когда мы работаем с максимальными потоками, целесообразно реализовать функцию, проверяющую, что величины притоков и истечений соответствуют в каждой вершине, а структуры данных непротиворечивы (см. упражнение 22.12). Программа 22.8. Вычисление стоимости потока________________________________ Эту функцию можно включить в программу 22.2. Она возвращает стоимость сетевого потока за счет суммирования произведения стоимости на величину потока для всех ребер, обладающих положительной пропускной способностью, позволяя при этом рассматривать ребра без пропускной способности как фиктивные. static int cost(Graph & G) { int x = 0; for (int v = O; v < G.V(); v++) { typename Graph:: adjIterator A(G, v); for (Edge* e = A.beg();! A.end(); e = A.nxt()) if (e-> from(v) & & e-> costRto(e-> w()) < C) x += e-> flow()*e-> costRto(e-> w()); } return x; }
Определение 22.9. Пусть задан поток в транспортной сети со стоимостями ребер, остаточная сеть (residual network) для этого потока содержит те же вершины, что и исходная сеть, и одно или два ребра этой остаточной сети соответствуют каждом ребру в исходной сети и определяются следующим образом: пусть для каждого ребра u-v в исходной сети f есть поток, с есть пропускная способность и х — стоимость. Если f положителен, ребро u-v включается в остаточную сеть, при этом ему присваивается пропускная способностью f, и стоимость -х; если {меньше, чем с, ребро u-v включается в остаточную сеть с пропускной способностью c-f, со стоимостью -х. Часть 5. Алгоритмы на графах
|