Введення
Завдання про максимальний потік є класичним і має безліч застосувань. Нагадаю постановку проблеми. Дано зважений орієнтований граф з неотрицательными вагами (пропускними здібностями). Виділено дві вершини: істок S і стік T такі, що будь-яка інша вершина лежить на шляху з S в T. Потоком назвемо функцію F: V x V з такими властивостями
- Обмеження пропускної здатності. Потік по ребру не може бути більше його (ребра) пропускної здатності.
- Антисиметричність. Для кожного ребра (u, v): F(u, v) = -F(v, u).
- Збереження потоку. Для кожної вершини (крім S і T), кількість потоку (від'ємного) дорівнює кількості вихідного потоку (додатного). Тобто, алгебраічна сума потоків для кожної вершини (крім S і T) дорівнює нулю.
У цьому пості ви можете ознайомитися з реалізацією поставленої проблеми.
Перейдемо безпосередньо до типових завдань, які зводяться до алгоритму знаходження максимального потоку в мережі. Часто виявити в таких завданнях потік дуже не просто.
Завдання
- Завдання щодо максимального паросполучення. На вхід дається 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 вершин, що відповідають кольору. З вершини відповідних кольору і проведемо всі ребра кольору і у входи кінців ребер. Знайшовши максимальний потік у такій мережі, отримаємо максимальну кількість шляхів, що задовольняють необхідну властивість.
Джерело: Харківська зимова школа з програмування, 2009, День 4
- Колекціонування монет. Є n колекціонерів і m видів монет. Для вступу в клуб, необхідно мати не менше однієї монети кожного типу. Ви (у Вас номер 1) можете змінюватися з колекціонерами наявними монетами. Будь-який колекціонер обміняє монету свою монету a на Вашу монету b, якщо у нього більше однієї монети типу a і немає жодної монети типу b. Ви, в свою чергу, можете порушувати це правило. Потрібно набрати якомога більше типів монет за відомою ситуацією у всіх колекціонерів.
Рішення
Побудуємо мережу. Створимо для кожного типу монет по одній вершині. Ці вершини будуть відповідати Вашим монетам. Потрібно зібрати якомога більше унікальних монет, тому проведемо ребро пропускної здатності 1 в стік з кожної такої вершини. У вершини, що відповідають монетам, які у Вас є спочатку, проведемо ребро, пропускна здатність якого дорівнює кількості таких монет у Вас.
Для кожного члена клубу (крім 1, тобто Вас) заведемо по одній вершині. Ця вершина може приймати не більше однієї монети, якої у нього немає і віддавати
не більше k-1 монети, яких у нього k (k > 1). Природно, член клубу віддає одну монету замість однієї отриманої.
Таким чином, в кожну таку вершину потрібно провести ребро пропускної здатності 1 з вершин відповідних монетам, яких немає у цього члена клубу. А з цих вершин потрібно провести ребра пропускною здатністю ki - 1 у вершину i, що відповідає монетам, яких у члена клубу більше однієї.
Побудована мережа відображає процеси обміну в клубі. Максимальний потік у такій мережі дорівнюватиме максимальній кількості монет, які могутність бути зібрані Вами.
Джерело: Харківська зимова школа з програмування, 2009, День 4
- Циркуляція. Система охолодження реактора являє собою набір труб, що з'єднують вузли. По трубах тече рідина, причому для кожної труби суворо визначено напрямок, в якому вона повинна по ній текти. Вузли системи охолодження занумеровані від 1 до N. Система охолодження повинна бути спроектована таким чином, щоб для кожного вузла за одиницю часу кількість рідини, що втікає у вузол, було дорівнює кількості рідини, що випливає з вузла. У кожної труби є пропускна здатність cij. Крім того, для забезпечення достатнього охолодження потрібно, щоб по трубі протікало не менше lij одиниць рідини за одиницю часу. Тобто для труби, що веде з i-го вузла в j-ий має виконуватися lij fij cij.
Дано опис системи охолодження. Потрібно з'ясувати, яким чином можна пустити рідину по трубах, щоб виконувалися всі зазначені умови.
Рішення
Це завдання на знаходження циркуляції в мережі з заданими нижніми обмеженнями на ребра. Якщо по ребру (u, v) повинен проходити потік у відрізку [l, r], то в перебудованій мережі буде три ребра (звідки, куди, вага): (u, v, r — l), (S, v, l), (u, T, l). S, T - додатково введені стік і істок відповідно. Фактично ми пропускаємо по ребру необхідний мінімальний потік, після чого балансуємо його так, щоб отримати циркуляцію.
Джерело: Харківська зимова школа з програмування, 2009, День 4
- Знову танці. На вечірку запрошені n хлопчиків і n дівчаток. Вони хочуть станцювати кілька раундів.
У кожному раунді гості діляться на n пар, що танцюють. Кожен гість повинен бути в деякій парі, кожна пара повинна складатися з одного хлопчика і однієї дівчинки. У кожному раунді кожен хлопчик повинен танцювати з іншою дівчинкою. Деякі хлопчики і дівчата не подобаються один одному. Кожен хлопчик може танцювати не більше ніж з k дівчатками, які йому не подобаються. Аналогічно кожна дівчинка може танцювати не більше ніж з k хлопчиками, які їй не подобаються.
Є інформація про те, чи подобаються один одному i-ий хлопчик і j-а дівчинка (1 i, j n). Знайти найбільшу кількість раундів, яку можна станцювати на вечірці.
Рішення
Розглянемо наступне завдання: чи можуть танці тривати в точності m раундів? Якщо ми зможемо відповісти на це питання, то бінарним пошуком знайдемо найбільше m, для якого проведення танців можливе.
Побудуємо граф, який має один істок і один стік (чорні вершини). Червоні вершини представляють хлопчиків, сірі - дівчаток. Якщо хлопчик і дівчинка подобаються один одному, то проведемо між ними ребро поодинокої пропускної здатності (на малюнку такими є два ребра - верхнє і нижнє). Інакше додамо сині і зелені вершини як показано на малюнку і встановимо пропускну здатність ребер між відповідними синіми і зеленими вершинами рівну 1.
Сині та зелені вершини утворюють «захисний» рівень. Зв'язок хлопчиків з дівчатками, які один одному не подобаються, проходитиме за ребрами захисного рівня. Кожен хлопчик може танцювати не більше ніж з k дівчатками, які йому не подобаються. Встановимо пропускну здатність ребер між червоними і синіми, зеленими і сірими вершинами рівну k. Таким чином, між кожним хлопчиком і кожною дівчинкою буде встановлено зв'язок через ребро або безпосередньо, або через вершини захисного рівня.
Танці повинні тривати в точності m раундів. Встановімо пропускну здатність ребер між витоком і червоними вершинами, а також між сірими вершинами і стоком рівну m.
Знаходимо максимальний потік у графі. Танці можуть тривати в точності m раундів тоді і тільки тоді, коли величина максимального потоку дорівнюватиме n * m, де n - кількість хлопчиків.
Джерело: Севастопольська літня школа з програмування, 2010, День 4
Ув'язнення
Ми розглянули мізерно малу частину неосяжної безлічі завдань, що зводяться до знаходження максимального потоку в мережі. І це не зачіпаючи максимальний потік мінімальної вартості. Такі завдання відрізняються своєю красою у вирішенні. Програмісту, знаючи стандартний алгоритм знаходження максимального потоку, залишається тільки побудувати граф, відповідний поставленій задачі і пустити потік.