Применения максимального потока: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Новая страница: «== Ссылки == * [http://jeffe.cs.illinois.edu/teaching/algorithms/book/11-maxflowapps.pdf Erickson J. — Applications of Flows and Cuts] * [https://neerc.if...»)
 
Нет описания правки
Строка 1: Строка 1:
== Минимальный разрез ==
Вычисляем максимальный поток.
Далее запускаем из истока dfs, который идёт только по рёбрам с ненулевой остаточной пропускной способностью.
Посещённые dfsом вершины составляют одну долю, непосещённые — другую, рёбра между ними составляют минимальный разрез. Величина минимального разреза равна величине максимального потока.
== Максимальное паросочетание в двудольном графе ==
Строим сеть: (исток), (количество вершин первой доли), (количество вершин второй доли), (сток).
Соединяем исток со всеми вершинами первой доли рёбрами пропускной способности 1.
Соединяем вершины первой доли с вершинами второй доли рёбрами пропускной способности 1, если соответствующее ребро было в исходном графе.
Соединяем все вершины второй доли со стоком рёбрами пропускной способности 1.
Размер максимального паросочетания равен величине максимального потока. В паросочетание входят рёбра между вершинами долей, нагруженные потоком.
== Количество рёберно-непересекающихся путей между a и b ==
Считаем, что рёбра исходного графа имеют пропускную способность 1.
Вычисляем максимальный поток из a в b, его величина равна ответу.
== Количество вершинно-непересекающихся путей между a и b ==
Ставим в соответствие каждой вершине исходного графа две вершины («входную» и «выходную»), соединённые ребром пропускной способности 1.
Если в исходном графе было ребро (x → y), до добавляем ребро (выход_x → вход_y) пропускной способности 1.
Вычисляем максимальный поток из выход_a в вход_b, его величина равна ответу.
== Есть ли путь из a в b и из b в c, не проходящий по одному ребру дважды ==
Считаем, что рёбра исходного графа имеют пропускную способность 1.
Соединяем a и c со стоком рёбрами пропускной способности 1, вычисляем максимальный поток между b и стоком, проверяем, что его величина равна 2.
== Можно ли замостить заданную клетчатую фигуру костями домино 1 × 2 ==
Мысленно раскрашиваем клетки фигуры в шахматном порядке. Строим сеть: (исток), (количество белых клеток), (количество чёрных клеток), (сток).
Соединяем исток со всеми белыми клетками рёбрами пропускной способности 1.
Соединяем белые клетки с соседними чёрными клетками рёбрами пропускной способности 1.
Соединяем все чёрные клетки со стоком рёбрами пропускной способности 1.
Вычисляем максимальный поток, проверяем, что его величина равна количеству клеток, делённому пополам.
== Ссылки ==
== Ссылки ==
* [http://jeffe.cs.illinois.edu/teaching/algorithms/book/11-maxflowapps.pdf Erickson J. — Applications of Flows and Cuts]
* [http://jeffe.cs.illinois.edu/teaching/algorithms/book/11-maxflowapps.pdf Erickson J. — Applications of Flows and Cuts]

Версия от 11:00, 31 мая 2021

Минимальный разрез

Вычисляем максимальный поток.

Далее запускаем из истока dfs, который идёт только по рёбрам с ненулевой остаточной пропускной способностью.

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

Максимальное паросочетание в двудольном графе

Строим сеть: (исток), (количество вершин первой доли), (количество вершин второй доли), (сток).

Соединяем исток со всеми вершинами первой доли рёбрами пропускной способности 1.

Соединяем вершины первой доли с вершинами второй доли рёбрами пропускной способности 1, если соответствующее ребро было в исходном графе.

Соединяем все вершины второй доли со стоком рёбрами пропускной способности 1.

Размер максимального паросочетания равен величине максимального потока. В паросочетание входят рёбра между вершинами долей, нагруженные потоком.

Количество рёберно-непересекающихся путей между a и b

Считаем, что рёбра исходного графа имеют пропускную способность 1.

Вычисляем максимальный поток из a в b, его величина равна ответу.

Количество вершинно-непересекающихся путей между a и b

Ставим в соответствие каждой вершине исходного графа две вершины («входную» и «выходную»), соединённые ребром пропускной способности 1.

Если в исходном графе было ребро (x → y), до добавляем ребро (выход_x → вход_y) пропускной способности 1.

Вычисляем максимальный поток из выход_a в вход_b, его величина равна ответу.

Есть ли путь из a в b и из b в c, не проходящий по одному ребру дважды

Считаем, что рёбра исходного графа имеют пропускную способность 1.

Соединяем a и c со стоком рёбрами пропускной способности 1, вычисляем максимальный поток между b и стоком, проверяем, что его величина равна 2.

Можно ли замостить заданную клетчатую фигуру костями домино 1 × 2

Мысленно раскрашиваем клетки фигуры в шахматном порядке. Строим сеть: (исток), (количество белых клеток), (количество чёрных клеток), (сток).

Соединяем исток со всеми белыми клетками рёбрами пропускной способности 1.

Соединяем белые клетки с соседними чёрными клетками рёбрами пропускной способности 1.

Соединяем все чёрные клетки со стоком рёбрами пропускной способности 1.

Вычисляем максимальный поток, проверяем, что его величина равна количеству клеток, делённому пополам.

Ссылки