Олимпиады по программированию

olympiads.ru

Дистанционные семинары
Оглавление
Как пользоваться
Система проверки задач
Регистрация, изменение настроек
Страница сдачи решений
Результаты
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике

Дистанционные семинары
по подготовке к олимпиадам по информатике

Занятие 19. Потоки в сетях. Алгоритм Форда-Фалкерсона.

Рассмотрим ориентированный граф. Будем рассматривать его как сеть труб, по которым некоторое вещество движется от истока, где оно производится с некоторой постоянной скоростью, к стоку, где оно потребляется с той же скоростью. На каждом ребре графа напишем число - пропускную способность трубы (т.е. максимальную скорость потока в данной трубе). Будем считать, что в вершинах вещество не накапливается - сколько приходит, столько и уходит (за исключением истока и стока). Это свойство называется законом сохранения потока.

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

Дадим несколько формальных определений.

Назовем сетью ориентированный граф G = (V,E), каждому ребру (u,v) которого поставлено в соответствие число c(u,v)>=0, называемое пропускной способностью ребра. В случае отсутствия ребра (u,v) в графе мы полагаем c(u,v)=0. В графе выделены две вершины: исток s и сток t.

Потоком в сети G назовем функцию f: VxV->R, обладающую следующими свойствами:

  • f(u,v)<=c(u,v)
  • f(u,v)=-f(v,u)
  • сумма по всем v из V f(u,v) равна 0 (для всех u из V\{s,t})
Величина f(u,v) может быть как положительной, так и отрицательной. Она определяет, сколько вещества движется из вершины u в вершину v (отрицательные значения соответствуют движению в обратную сторону).

Величина потока определяется как сумма значений f(s,v) по всем v из V.
Задача о максимальном потоке состоит в следующем: для данной сети G с истоком s и стоком t найти поток максимальной величины.

Остаточной пропускной способностью из u в v называется величина
cf(u,v) = c(u,v) - f(u,v)
Она определяет,сколько еще вещества может пропустить ребро из u в v.
Сеть, составленную из ребер с пропускной способностью, равной остаточной пропускной способности cf(u,v), назовем остаточной сетью сети G, порожденной потоком f. Ее ребра называются остаточными ребрами.

Дополняющем путем назовем простой путь (т.е. путь проходящий по каждой вершине не более одного раза) из истока s в сток t в остаточной сети Gf.
Остаточной пропускной способностью дополняющего пути p назовем величину
cf = min {cf(u,v): (u,v) принадлежит p}.

Рассмотрим теперь один из алгоритмов построения максимального потока.

Алгоритм Форда-Фалкерсона:

  • Положить начальный поток равным 0.
  • Пока существует путь p в остаточной сети Gf, пустить по нему поток велиины cf(p).

Времы работы данного алгоритма зависит от того, как ищется путь p. В принципе, алгоритм может вообще не остановиться, если величина потока будет расти все более и более мелкими шагами, так и не достигнув максимума. Однако, если выбирать дополняющий путь поиском в ширину, времы работы алгоритма будет O(VE2) (V - количество вершин в сети, а E - количество ребер).

Задача 19-1. Симпатичные таблицы