Файл: Курсач ебаный.docx

Шаг 1. Если не существует пути из источника в сток, то положить j=0 и перейти к шагу 4, иначе выбрать непустое множество T непересекающихся по дугам путей из a в b. Если e₁,e₂,…,e_k – путь из T, т.е. последовательность дуг, то положить j(e₁)= j(e₂)=…= j(e_k)=min{a(e₁),…,a(e_k)}. Для дуг e, через которые не проходят пути из T, положитьj(e)=0. В результате получаем ненулевой поток j через сеть (G,a).

Шаг 2. Исходя из сети (G,a) и потока j построить сеть (G′,a′) следующим образом. Граф G^’ будет иметь те же вершины, что и граф G. Если e – дуга графа G и a(e) - j(e)¹0, то e – дуга графа G′ и a′(e)=a(e) - j(e). Если e – дуга графа G и j(e)¹0, то вводим дугу обратной ориентации, нежели e, и полагаем a′() = j(e). В случае, когда возникают кратные дуги e₁ и e₂, то вводим вместо них одну дугу e и полагаем a′(e)=a′(e₁) + a′(e₂).

Шаг 3. Если в сети (G′,a′) не существует пути из a в b, то перейти к шагу 4, иначе в сети (G’,a’) построить ненулевой поток j’ так, как это предписано шагом 1. Для сети (G,a) положить j=j+j’ и перейти к шагу 2.

Шаг 4. Выдать j. Конец работы алгоритма.

На примере сети, изображенной на рис 6.22, проиллюстрируем работу алгоритма. В качестве множества T на первом шаге алгоритма выбрано множество из двух путей: a,v₁,v₄,b и a,v₂,v₅,b.

Рис. 6.22

Рис. 6.23

На рис. 6.23 представлена сеть (G′,a′) полученная после выполнения шага 2 из сети на рис. 6.22 с указанным (в скобках) потоком j′. В качестве множества T для построения потока j′ взято множество, состоящее из одного пути: a,v₃,v₅,v₂,v₆,b. Поток j+j′ для сети (G,a) изображен на рис. 6.24. Этим завершен один проход алгоритма. Обратим внимание на то, что для e=(v₂,v₅) (j+j′)(e)=j(e)–j′()=1.

Рис. 6.24

Рис. 6.25

Сеть построенная на шаге 2 второго прохода алгоритма, уже не имеет (a,b) – путей (см.рис. 6.25). Следовательно, на рис. 6.24 изображен максимальный поток.

Задачи

Задача о максимальном паросочетании. На вход дается N — количество мальчиков, M — количество девочек и список, какой мальчик с какой из девочек хочет танцевать (таких может быть несколько). Надо определить максимальное количество одновременно танцующих пар.

Решение

Для решения этой задачи можно использовать алгоритм Куна, но раз уж мы взялись сводить все к потоку — давайте это сделаем. Для этого не хватает истока и стока. Давайте их добавим! «Слева» добавим фиктивную вершину и проведем ребра ко всем мальчикам весом в 1. От мальчиков к девочкам уже есть ребра проставим им тоже цену 1. И от девочек ребра к стоку тоже ценой 1. Ответом к задаче является величина максимального потока между истоком и стоком.

Испорченный паркет. У паркета NxM, некоторые клетки могут быть испорчены. Их необходимо закрыть новыми плитками. Плитки бывают размером 2х1 (можно поворачивать, но нельзя разрезать) ценой А, и 1х1 ценой B. Спрашивается, какую минимальную сумму нужно потратить, что бы заложить испорченные плитки паркета. Естественно, новые плитки не должны перекрывать никакие другие плитки.

Решение

Для начала, убедимся, что 2*B>A. Иначе, все выгодней замостить только плитками 1х1 и больше нечего считать. Далее наша задача максимизировать количество плиток ценой А. Раскрасим наш паркет по принципу шахматной доски. Очевидно, что тогда один конец плитки 2х1 будет лежать на черной клетке, другой — на белой. Итак, построим двудольный граф, одна доля которого будет содержать белые клетки, другая — черные. Ребра весом в 1 проведем между граничащими клетками. Добавим исток с ребрами в белые вершины весом в бесконечность (довольно распространенный прием) и сток с ребрами из черных клеток весом тоже в бесконечность. Пускай f — величина найденного максимального потока между истоком и стоком. Тоесть мы нашли количество плиток 2х1. Ответом к задаче будет величина f*A+(K-f)*B, где K — общее количество испорченных клеток. Источник: Харьковская зимняя школа по программированию, 2009, День 3

Задача живопись. Дана матрица N*M с клетками, покрашенными либо в черный, либо в белый цвета. W — цена перекраски черного квадрата в белый, B — белого в черный. После перекраски, между всеми соседними квадратами разных цветов нужно провести серую линию, ценой G. Надо так отпимально перекрасить матрицу (или ничего не делать), что бы потратить минимальную сумму.

Решение

Крайний случай: если матрица вся одного цвета — ответ 0. Добавим фиктивные исток и сток. От истока ко всем белым вершинам проведем ребра, весом в B (цена перекраски в черный). От черных вершин ко стоку проведем ребра, весом в W (цена перекраски в белый). И между всеми соседними вершинами (будь они одного или разных цветов) — ставим ребро весом в G (серая линия). Величина максимального потока будет ответом на задачу. Источник: Всеукраинская школьная олимпиада по информатике, 2007, День 1

Задача с ограничением на вершины. Пусть надо найти величину максимального потока и на вершины наложено ограничение, сколько они могут пропустить.

Решение

Все, что нам надо — это разделить каждую вершину на две, и между ними поставить ребро, весом в ограничение пропускной способности данной вершины

Минимальный разрез. Дан граф. Сколько вершин надо удалить, что бы не существовало пути из A в B?

Решение

В классической задаче о минимальном разрезе удалять нужно ребра. Не проблема! Разобьем вершины на 2, и поставим между ними ребро, весом в 1. Тогда ответ к задаче — нахождение минимального разреза в графе (что и есть максимальным потоком). Источник: Харьковская зимняя школа по программированию, 2009, День 3

Сочинитель стихов. Имеется детерминированный конечный автомат с одним начальным состоянием A и одним конечным B. Каждый переход задается тройкой чисел (i, j, k), переход из состояния i в состояние j по ребру k. После перехода по автомату из i в j по ребру k, стираются все переходы из i по ребру k, а также все переходы в j по ребру k. Требуется вывести количество путей из A в B по такому автомату.

Решение

Задача сводится к нахождению максимального количества путей, причем из одной вершины не выходят более одного ребра одного цвета. Сведем задачу к нахождения максимального потока. Для каждой вершин создадим k+1 вершину в перестроенной сети. Первая вершина будет входом, остальные вершины будут представлять цвета. Из вершины входа проведем по ребру пропускной способностью 1 в каждую из k вершин, соответствующих цвету. Из вершины соответствующих цвету i проведем все ребра цвета i во входы концов ребер. Найдя максимальный поток в такой сети, получим максимальное количество путей удовлетворяющих требуемому свойству. Источник: Харьковская зимняя школа по программированию, 2009, День 4

Коллекционирование монет. Есть n коллекционеров и m видов монет. Для вступления в клуб, необходимо иметь не меньше одной монеты каждого типа. Вы (у Вас номер 1) можете меняться с коллекционерами имеющимися монетами. Любой коллекционер обменяет монету свою монету a на Вашу монету b, если у него больше одной монеты типа a и нету ни одной монеты типа b. Вы, в свою очередь, можете нарушать это правило. Нужно набрать как можно больше типов монет по известной ситуации у всех коллекционеров.

Решение

Построим сеть. Создадим для каждого типа монет по одной вершине. Эти вершины будут соответствовать Вашим монетам. Нужно собрать как можно больше уникальных монет, поэтому проведем ребро пропускной способности 1 в сток из каждой такой вершины. В вершины, соответствующие монетам, которые у Вас есть изначально, проведем ребро, пропускная способность которого равна количеству таких монет у Вас. Для каждого члена клуба (кроме 1, тоесть Вас) заведем по одной вершине. Эта вершина может принимать не более одной монеты, которой у него нет и отдавать не более k-1 монеты, которых у него k (k > 1). Естественно, член клуба отдает одну монету взамен одной полученной. Таким образом, в каждую такую вершину нужно провести ребро пропускной способности 1 из вершин соответствующих монетам, которых нет у этого члена клуба. А из этих вершин нужно провести ребра пропускной способностью k_i — 1 в вершину i, соответствующую монетам, которых у члена клуба больше одной. Построенная сеть отражает процессы обмена в клубе. Максимальный поток в такой сети будет равен максимальному количеству монет, которые могуть быть собраны Вами. Источник: Харьковская зимняя школа по программированию, 2009, День 4

Циркуляция. Система охлаждения реактора представляет собой набор труб, соединяющих узлы. По трубам течет жидкость, причем для каждой трубы строго определено направление, в котором она должна по ней течь. Узлы системы охлаждения занумерованы от 1 до N. Система охлаждения должна быть спроектирована таким образом, чтобы для каждого узла за единицу времени количество жидкости, втекающей в узел, было равно количеству жидкости, вытекающей из узла. У каждой трубы имеется пропускная способность c_ij. Кроме того, для обеспечения достаточного охлаждения требуется, чтобы по трубе протекало не менее l_ij единиц жидкости за единицу времени. То есть для трубы, ведущей из i-го узла в j-ый должно выполняться l_ij ≤ f_ij ≤ c_ij. Дано описание системы охлаждения. Нужно выяснить, каким образом можно пустить жидкость по трубам, чтобы выполнялись все указанные условия.

Решение

Это задача на нахождение циркуляции в сети с заданными нижними ограничениями на ребра. Если по ребру (u, v) должен проходить поток в отрезке [l, r], то в перестроенной сети будет три ребра (откуда, куда, вес): (u, v, r — l), (S, v, l), (u, T, l). S, T — дополнительно введенные сток и исток соответственно. Фактически мы пропускаем по ребру необходимый минимальный поток, после чего балансируем его так, чтобы получить циркуляцию. Источник: Харьковская зимняя школа по программированию, 2009, День 4