VIP-мережа#13056

VIP-мережа (Розбір)

Розглянемо максимальну можливу величину заторів. Якщо жодне місто не підвищувати до статусу "VIP", кожна дорога має значення $3$ . Отже, початкова сумарна величина мережі дорівнює $3 \cdot M$ 3 \cdot M.

Що відбувається, коли Фаді підвищує одне місто $u$ до статусу "VIP"?

Кожна дорога, що з'єднана з містом $u$ , змінює свій стан з (Standard–Standard) на (VIP–Standard). Її значення зменшується з $3$ до $2$ . Це зменшує сумарний показник мережі на $1$ для кожної дороги, що з'єднана з $u$ .
Якщо місто $v$ на іншому кінці дороги також підвищене до статусу "VIP", стан дороги змінюється з (VIP–Standard) на (VIP–VIP). Її значення зменшується з $2$ до $1$ . Це зменшує сумарний показник ще на $1$ .

Ключове спостереження: Підвищення міста до статусу "VIP" незалежно зменшує сумарний показник мережі рівно на $1$ для кожної дороги, що з ним з'єднана. У термінах графів, підвищення вершини $u$ зменшує сумарний показник на $degree (u)$ .

Отже, щоб мінімізувати сумарну величину заторів, потрібно максимізувати загальне зменшення. Обчислюємо степінь усіх $N$ міст, сортуємо їх у порядку спадання і вибираємо $K$ міст з найбільшими степенями.

Мінімальний показник = 3 \cdot M - i \in Top K \sum degree [i]

\text{Мінімальний показник} = 3 \cdot M - \sum_{i \in \text{Top } K} \text{degree}[i]

Аналіз складності:

Часова складність: $O (N lo g N + M)$ \mathcal{O}(N \log N + M) на кожен набір вхідних даних через сортування степенів вершин.
Пам'яттєва складність: $O (N + M)$ \mathcal{O}(N + M) для зберігання списку суміжності / таблиці степенів.