P5805 [SEERC 2019] Graph and Cycles

There is an undirected complete graph with $n$ vertices and edge weights, where $n$ is odd. A *cycle edge group* of size $k$ is an array of edges $[e_1, e_2, \dots, e_k]$ that satisfies: - $k$ is greater than $1$. - For any integer $i$ in $[1, k]$, the edge $e_i$ shares exactly one common endpoint with each of $e_{i-1}$ and $e_{i+1}$ (where $e_0 = e_k$ and $e_{k+1} = e_1$). Obviously, the edges in a cycle edge group form a cycle in the graph. Define a function $f(e_1, e_2)$ for two edges $e_1, e_2$ as the larger of their edge weights. Define the *value* of a cycle edge group $C = [e_1, e_2, \dots, e_k]$ as the sum of $f(e_i, e_{i+1})$ over all integers $i$ in $[1, k]$ (where $e_{k+1} = e_1$). Define a *cycle decomposition* of a graph as a set of pairwise disjoint cycle edge groups whose union contains all edges of the graph. Define the *value* of a cycle decomposition as the sum of the values of all cycle edge groups in it. A graph may have multiple cycle decompositions. Given a graph, your task is to find the cycle decomposition with the minimum value and output this minimum value.

The first line contains an integer $n \ (3 \leq n \leq 999, n \bmod 2 = 1)$, representing the number of vertices in the graph. The next $\frac{n\cdot (n-1)}{2}$ lines each contain three integers $u, v$ and $w \ (1 \leq u, v \leq n, u \neq v, 1 \leq w \leq 10^9)$, indicating that there is an edge of weight $w$ between vertex $u$ and vertex $v$.

Output one integer, representing the value of the minimum-value cycle decomposition of the given graph.

In the following sample explanations, edges are numbered in input order, and $e_i$ denotes the $i$-th edge in the input order. In the first sample, the only cycle decomposition is $S = \{ [e_1, e_2, e_3] \}$. $f(e_1, e_2) + f(e_2, e_3) + f(e_3, e_1) = 1 + 1 + 1 = 3$. In the second sample, an optimal cycle decomposition is $S = \{ [e_3, e_8, e_9], [e_2, e_4, e_7, e_{10}, e_5, e_1, e_6] \}$. The value of the cycle edge group $[e_3, e_8, e_9]$ is $12$, and the value of $[e_2, e_4, e_7, e_{10}, e_5, e_1, e_6]$ is $23$, so the value of the cycle decomposition is $35$. Translated by ChatGPT 5