завдання п'ятірки
- A. Максимальний потік 0
- B. Максимальний потік 2
- C. Таксі
- D. Симпатичні таблиці
- E. Замощення Доміношки
Максимальний потік 0
Максимальний потік 2
Завдання вирішується будь-яким швидким алгоритмом знаходження максимального потоку, до яких відноситься, наприклад, і алгоритм Дініца, опис та реалізацію якого можна знайти тут .
таксі
Розбір В.Гольдштейна: Розглянемо граф, в якому вершинами є замовлення. Якщо машина встигає відпрацювати один замовлення i, а потім встигнути на замовлення j, то проведемо ребро з i в j. Тоді задача зводиться до розбиття ациклического графа на безліч непересічних шляхів. Це можна зробити, побудувавши двочастковий граф, в якому буде в два рази більше вершин з такою ж матрицею суміжності. Знайдемо в цьому графі максимальне паросполучення. Кожне ребро паросполучення буде деяким ребром в одній із колій. Вершини першої частки, які входять в паросочетание, будуть стартовими вершинами шляхів. Аналогічно, вершини першої частки - кінцевими вершинами шляхів. Таким чином, відповіддю буде NM, де N - кількість вершин, а M - розмір максимального паросполучення.
симпатичні таблиці
По-перше, якщо відняти вже розставлені числа з обмежень на суму чисел у відповідних рядках і шпальтах, то задача зведеться до аналогічної. Відповідь буде відрізнятися рівно на ці числа. Значить, далі будемо вважати, що всі спочатку розставлені числа рівні 0.
Побудуємо мережу з N + M + 2 вершин. Вершинами будуть рядки матриці, її стовпці і дві додаткові вершини: витік і стік. З витоку будуть вести дуги в вершини, відповідні рядках з пропускною спроможністю Ri. З вершин, відповідних стовпцях, йтимуть дуги в стік з пропускною спроможністю Cj. Вершини, що відповідають i -му рядку і j -му стовпцю будуть з'єднані дугою тоді і тільки тоді, коли на перетині i -го рядка і j-го стовпця в оригінальній матриці стояло число -1. Пропускна здатність таких дуг буде дорівнює нескінченності. Максимальний потік в цій мережі і буде відповіддю на поставлене завдання.
Мережа можна не будувати явно, а продовжувати працювати з матрицею.
замощення Доміношки
Розбір І.Галаева : Позначимо через F загальна кількість вільних клітин. Тоді якщо 2 · b ≤ a, то відповіддю буде F · b. Інакше нам потрібно максимізувати кількість доміношек, які можна розмістити на вільних клітинах дошки. Для цього побудуємо граф, вершинами в якому будуть представлені вільні клітини матриці, а ребро буде існувати, якщо клітини суміжні по горизонталі або вертикалі.
Зауважимо, що цей граф двочастковий і довільне паросочетание в даному графі задає відповідність між деякими суміжними вільними клітинами, тобто задає деяку прихильність доміношек. Таким чином задача зводиться до знаходження максимального паросполучення в дводольному графі і може бути вирішена алгоритмом Куна.
Відповіддю буде M · a + (F - 2 · M) · b, де M - кількість ребер в максимальному паросочетание.
По завершенню тижні можна в цій темі акумульовано висловитися або обговорити.
Найбільш цінні ідеї будуть перенесені вище, як розбори учасників.
