Козак Вус та картопля#141

Козак Вус та картопля (Розбір)

Що саме мінімізуємо. Козаків у кожному місті нескінченно багато, і всі мішки несуть одночасно. Тому загальний час — це не сума робіт, а найдовша окрема подорож. Задача формулюється так: розподілити мішки по бункерах з урахуванням місткостей так, щоб максимальна відстань «місто його бункер» була мінімальною.

Двійковий пошук за відповіддю. Зафіксуємо межу . Тоді кожне місто може користуватися лише тими бункерами, до яких відстань не перевищує , і питання стає суто транспортним: чи можна розвезти всі мішки, не перевищивши місткостей?

Перевірка — умова Голла, а не потік. Бункерів щонайбільше — це запрошення перебрати всі 2^{18} підмножин. Транспортна задача здійсненна тоді й лише тоді, коли для кожної підмножини бункерів

\sum_{\substack{\text{міста, чиї доступні бункери} \\ \text{всі лежать усередині } S}} p_i \;\le\; \sum_{j \in S} c_j .

Тобто мішки, яким нікуди подітися, окрім , мають туди вміститися. Це дефектна форма умови Голла для транспортної задачі; запускати потік не треба.

Рахується це швидко. Для кожного міста визначаємо маску доступних бункерів і додаємо p_i у комірку цієї маски. Далі одним проходом «сум по підмножинах» (SOS-динаміка, \mathcal{O}(2^s \cdot s)) отримуємо для кожної сумарну пропозицію міст із маскою і порівнюємо з місткістю . Місто з p_i > 0 і порожньою маскою одразу робить непридатним.

Відстані. Потрібні відстані від міст до бункерів, а дороги односторонні. Тому будуємо обернений граф і запускаємо по одному Дейкстрі з кожного бункера — за s \le 18 запусків отримуємо всі потрібні відстані. На m \le 6\cdot10^5 ребрах це \mathcal{O}(s \cdot m \log n).

Двійковий пошук. Кандидатами на відповідь є лише самі значення відстаней (їх \le n \cdot s), тож сортуємо їх і шукаємо двійковим пошуком по індексу. Якщо навіть при нескінченному умова Голла порушується (сумарна місткість менша за кількість мішків або якесь місто взагалі не має шляху до бункера), виводимо .

Складність — \mathcal{O}\bigl(s\,m \log n + \log(ns)\cdot(n + 2^s s)\bigr). Мішків до 10^{14} сумарно, місткості до 10^9, відстані до 10^{14} — усе в -бітних.