Версия для печати темы
Нажмите сюда для просмотра этой темы в обычном формате
Форум «Всё о Паскале» _ Задачи _ Задача об источниках и потребителях
Автор: Maxx 5.12.2006 16:28
Решить задачу об источниках и потребителях, сведя ее к задаче построения максимального потока в транспортной сети и используя первый алгоритм построения максимального потока:
Данные: транспортная сеть D, заданная матрицей пропускных способностей дуг.
Результат: максимальный поток в сети.
1. Полагаем i = 0. Пусть 0 – любой допустимый поток в транспортной сети D (напри-мер, полный или нулевой).
2. По сети D и потоку i строим орграф приращений I(D, i).
3. Находим простую цепь i, являющуюся минимальным путем из v1 в vn в нагружен-ном орграфе I(D, i) (можно использовать любой описанный выше алгоритм). Если длина этой цепи равна , то поток i максимален и работа алгоритма заканчивается. В противном случае увеличиваем поток вдоль цепи i на максимально допусти-мую величину ai > 0, где aiZ (прибавляя ее для каждой дуги xX, через которую проходит цепь i, к уже имеющейся величине потока по дуге x, если дуга x входит в i, и вычитая, если дуга x* входит в i), такую, что при этом сохраняется условие до-пустимого потока. В результате меняется поток в транспортной сети D, т.е. от пото-ка i переходим к потоку i+1, который является допустимым, и при этом величина его увеличивается на ai. Присваиваем i = i + 1 и переходим к шагу 2.
Автор: мисс_граффити 5.12.2006 23:20
можно приступать к решению? 
показывай, что сам пробовал делать