Дорожня система Ужляндії#85

Дорожня система Ужляндії (Editorial)

Спершу перекладемо «властивість непарності» звичною мовою теорії графів. Замкнутий шлях C_1, \ldots, C_K з C_1 = C_K має довжину (кількість елементів послідовності), а ребер у ньому K - 1. Вимога, щоб була непарною, означає, що будь-який цикл має парну кількість ребер. А граф, у якому всі цикли парні, — це в точності дводольний граф.

Отже, треба додати якнайбільше ребер, зберігши дводольність (і простоту графа).

Дводольний граф — це розбиття вершин на дві частки так, що всі ребра йдуть між частками. Якщо в частках і вершин відповідно та , то максимальна кількість ребер — це повний дводольний граф, тобто |A| \cdot |B|. Тому відповідь дорівнює

\max |A| \cdot |B| - M.

Залишилось зрозуміти, які розбиття взагалі досяжні. Усередині кожної компоненти зв'язності розфарбування в два кольори визначено однозначно з точністю до обміну кольорів. Тому для компоненти з розмірами часток (c_1, c_2) ми вільні віднести до або c_1, або c_2 вершин — незалежно від інших компонент. Ізольовані вершини дають вибір .

Звідси алгоритм:

  1. обходом у глибину (або ширину) розфарбуємо кожну компоненту у два кольори й запам'ятаємо пару (c_1, c_2);

  2. задачею про рюкзак з'ясуємо, які значення досяжні: булева динаміка — чи можна набрати рівно вершин у першу частку, беручи з кожної компоненти або c_1, або c_2;

  3. серед досяжних візьмемо той, що максимізує s \cdot (N - s), тобто найближчий до ;

  4. віднімемо вже наявні ребер.

Динаміку зручно реалізувати бітовою множиною (bitset у C++), і тоді крок для компоненти — це два зсуви та побітове АБО. Складність — \mathcal{O}(N^2/64 + M), що при N \le 10^4 цілком швидко.

Добуток |A| \cdot |B| сягає 2.5 \cdot 10^7, тому переповнення не загрожує, але 64-бітний тип не завадить.