Граф і цикли#11283
Маємо неорієнтований зважений повний граф з вершинами, де є непарним числом.
Циклічний масив розміру визначається як масив ребер [e[1], e[2], ..., e[k]], що задовольняє наступні умови:
більше .
Для кожного від до ребро e[i] має рівно одну спільну вершину з ребром e[i-1] і одну спільну вершину з ребром e[i+1], причому ці вершини різні (вважайте e[0] = e[k], e[k+1] = e[1]).
Очевидно, що ребра в циклічному масиві утворюють цикл.
Функція (e[1], e[2]) визначається як максимум між вагами ребер e[1] і e[2].
Нехай у нас є циклічний масив = [e[1], e[2], ..., e[k]]. Ціна циклічного масиву визначається як сума (e[i], e[i+1]) для всіх від до (e[k+1] = e[1]).
Циклічне розбиття графа - це набір неперетинних циклічних масивів, об'єднання яких містить усі ребра графа. Ціна циклічного розбиття - це сума цін його масивів.
Існує багато можливих циклічних розбиттів графа. Ваше завдання - знайти циклічне розбиття з мінімальною ціною і вивести цю ціну.
Перший рядок містить одне ціле число (3 \le n \le 999, непарне) - кількість вершин у графі.
Кожен з наступних n \cdot (n - 1) / 2 рядків містить три цілі числа: , і (1 \le u, v \le n, u \neq v, 1 \le w \le 10^9), що означають, що між вершинами і є ребро з вагою .
Виведіть одне ціле число - мінімально можливу ціну циклічного розбиття графа.
Приклад 1
Приклад 2
Пронумеруємо ребра в порядку їх появи у вхідних даних. Позначимо через e[i] ребро, яке з'являється -им у вхідних даних.
Єдиним можливим циклічним розбиттям графа в першому прикладі є = {[e[1], e[2], e[3]]}: (e[1], e[2]) + (e[2], e[3]) + (e[3], e[1]) = 1 + 1 + 1 = 3.
Оптимальне циклічне розбиття графа у другому прикладі: = {[e[3], e[8], e[9]], [e[2], e[4], e[7], e[10], e[5], e[1], e[6]]}. Ціна [e[3], e[8], e[9]] дорівнює , ціна [e[2], e[4], e[7], e[10], e[5], e[1], e[6]] дорівнює , тому загальна ціна розбиття дорівнює .