Тренування

ТРЕНування

Мирко і Славко усердно тренуються перед щорічним веломарафоном для тандемів, який пройде в Хорватії. Їм потрібно обрати маршрут для тренувань.

В країні N міст і M доріг. Кожна дорога з’єднує два міста, і по ній можна їхати в обох напрямках. Рівно N−1 з цих доріг є мощеними, а решта доріг — немощені стежки. На щастя, мережу доріг влаштовано таким чином, що довільну пару міст з’єднує шлях, що складається тільки з мощених доріг. Другими словами, N міст і N−1 мощених доріг утворюють структуру дерева.

Додатково відомо, що в кожному городі закінчується не більше 10 доріг.

Тренувальний маршрут починається в деякому місті, проходить по деяким дорогам та закінчується в тому же місті, де почався. Мирко і Славко люблять відвідувати нові міста, так що вони ввели правило: ніколи не проїжджати через одне й те саме місце, а також по одній і тій самій дорозі двічі. Тренувальний маршрут може починатись в довільному місті і не зобов’язаний проходити через всі міста.

В тандемі їхати на задньому сидінні легше, тому що велосипедист позаду захищений від вітру партнером, що сидить попереду. Із-за цього Мирко і Славко міняються місцями в кожному місті. Щоб отримати однакове навантаження на тренуванні, вони повинні обрати маршрут з парною кількістю доріг.

Суперники Мирка і Славка вирішили заблокувати деякі стежки, щоб було не можливо побудувати тренувальний маршрут, що задовольняє перераховані вимоги. Для кожної стежки відомо цену її блокування (додатне ціле число). Мощені дороги блокувати неможна.

Завдання

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

Вхідні дані

Перший рядок вхідних даних містить два цілих числа N і M (2 ≤ N ≤ 1 000, N−1 ≤ M ≤ 5 000), що задають кількість міст і загальну кількість доріг.

Кожен з наступних M рядків містить три цілих числа A, B і C (1 ≤ A ≤ N, 1 ≤ B ≤ N,
0 ≤ C ≤ 10 000), що описують одну дорогу. Числа A і B є різними і визначають міста, що напряму з’єднані дорогою. Якщо C=0 — дорога є мощеною; інакше — це стежка, і число C задає ціну блокування дороги.

В кожному місті закінчується не більше 10 доріг. Два міста з’єднані напряму не більше ніж однією дорогою.

Вихідні дані

Вихідні дані мають мстити з одного цілого числа — найменшої загальної вартості, як описано вище.

Система оцінювання

В тестах, які буде в сумі оцінено в 30 балів, мощені дороги будуть утворювати ланцюг (тобто ніяке місто не буде кінцем трьох або більше мощених доріг).

Детальний відгук системы що тестує
на відісланий роз’язок

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

ПРИКЛАДИ

вхідні дані 5 8 2 1 0 3 2 0 4 3 0 5 4 0 1 3 2 3 5 2 2 4 5 2 5 1 вихідні дані 5

вхідні дані 9 14 1 2 0 1 3 0 2 3 14 2 6 15 3 4 0 3 5 0 3 6 12 3 7 13 4 6 10 5 6 0 5 7 0 5 8 0 6 9 11 8 9 0 вихідні дані 48

Розташування доріг і міст у першому прикладі. Мощені дороги виділено жирним.

У Мирка і Славка є п’ять можливих маршрутів. Якщо дороги 1-3, 3-5 і 2-5 заблоковано, Мирко і Славко не можуть використовувати жоден з цих маршрутів. Вартість блокування цих трьох доріг - 5. Також можна заблокувати тільки 2 дороги, 2-4 і 2-5, але це дасть більшу вартість - 6.

РОЗв’язок

Перевірка існування непарного циклу в графі є добре відомою проблемою задачею. В графі немає непарного циклу тоді і тільки тоді, коли граф є дводольним. З іншого боку, задача виявлення непарного циклу не є широко відомою.

Маємо граф, що складається з N вершин та M ребер. Точно N−1 ребер помічені як ребра дерева та вони формують дерево. Ребро, яке не є ребром дерева, будемо називати недерев’яними. Кожне недерев’яне ребро має асоційовану з ним вагу.

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

Щоб описати модельний розв’язок, спершу зробимо декілька зауважень відносно структури графа з яким ми працюємо.

· Парні й непарні ребра

Розглянемо не дерев’яне ребро e={A, B}. Визначимо шлях у дереві для цього ребра як єдиний шлях з A до B, що складається тільки з ребер дерева. Якщо довжина шляху є парною, будемо казати, що це парне ребро, інакше – непарне. Будемо TP(e) позначати шлях у дереві для ребра e.

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

· Відношення між двома парними ребрами

Деякі парні ребра можуть входити до графу. Однак, якщо ми включимо декілька парних ребер, може утворитися парний цикл. Точніше кажучи, якщо e1 та e2 є парними ребрами, такими що TP(e1) та TP(e2) мають спільне ребро, тоді додавання в граф разом e1 та e2 обов’язково утворить парний цикл.

Щоб намітити шлях доведення цього твердження, розглянемо два непарних цикли, що утворені e1 та e2 разом з їх відповідними шляхами у дереві. Якщо ми викинемо всі спільні ребра з цих циклів, то отримаємо шляхи P1 та P2. Парність P1 дорівнює парності P2, оскільки ми видалили однакову кількість ребер з двох початково непарних циклів. Оскільки P1 та P2 також мають однакові кінцеві точки, ми можемо об’єднати їх в один великий парний цикл.

· Ребра дерева, що містяться в непарних циклах

Як прямий наслідок попереднього твердження, ми можемо заключити, що кожне ребро дерева може міститись як найбільше в одному непарному циклі.

Відповідно, якщо ми додаємо тільки парні ребра до дерева таким чином, що кожне ребро з дерева міститься в не більш як в одному непарному циклі, ми ніколи не утворимо парний цикл. Ідея доведення така. Якщо існує парний цикл, він має містити один або більше недерев’яних ребер. Неформально, якщо він містить рівно одне не дерев’яне ребро, це суперечить припущенню, що додавались тільки парні ребра; якщо він містить два або більше недерев’яних ребер, ми увійдемо у суперечність з другим припущенням.

· Модельний розв’язок

Тепер ми можемо використати наші спостереження для розробки розв’язку, з використанням ідеї динамічного програмування. Станом буде піддерево заданого дерева. Для кожного стану ми підрахуємо вагу максимального за вагою набора парних ребер, що можуть бути додані до піддерева, зберігаючи властивість що кожне ребро з дерева міститься в не більш ніж одному непарному циклі. Розв’язком задачі буде вага, отримана для стану, що задає початкове дерево.

Щоб отримати рекурсивну залежність, розглянемо всі парні ребра зі шляхами у дереві, що проходять через корінь дерева.

Ми можемо обрати одну з наступних дій:

(1) Ми не добавляємо ніякого парного ребра, чий шлях у дереві проходить через корінь дерева. У цьому випадку, ми можемо видалити корінь та продовжити обчислення оптимального розв’язку для кожного з піддерев, отриманих після видалення кореневої вершини.

(2) Ми обираємо парне ребро e, чий шлях у дереві проходить через корінь дерева. та додаємо його до дерева. Потім ми видаляємо всі ребра з дерева, що належать TP(e) (оскільки тепер вони містяться в одному непарному циклі), та, остаточно, ми обчислюємо оптимальну розв’язок для піддерев, що отримані після видалення шляху у дереві. Додамо w(e) до загальної суми.

Використаємо дерево на мал..1 як приклад. Мал. 2 ілюструє випадок (1) у рекурсивній залежності (було обрано не додавати ребро, чий шлях у дереві проходить через корінь дерева). Мал. 3 ілюструє випадок (2) рекурсивного відношення, коли ми включаємо ребро e={7, 9} до графа.

Мал 1

Мал 2

Мал 3

У залежності від того, як проводиться декомпозиція дерева, всі піддерева, які виникають як підзадачі, можуть бути подані цілим числом та бітовою маскою. Ціле задає індекс кореня піддерева, у той час як бітова маска визначає, які сини кореневого вузла видалені з піддрева.

Таким чином, загальна кількість можливих станів є обмежено. значенням N・2K, де K – це максимальна ступінь вузла.

У залежності від деталей реалізації, складність алгоритму може змінюватись. У офіціальній реалізації складність - O(M log M + MN + M・2K).