406382: GYM102392 J Graph and Cycles

There is an undirected weighted complete graph of $$$n$$$ vertices where $$$n$$$ is odd.

Let's define a cycle-array of size $$$k$$$ as an array of edges $$$[e_1,e_2,\ldots ,e_k]$$$ that has the following properties:

• $$$k$$$ is greater than $$$1$$$.
• For any $$$i$$$ from $$$1$$$ to $$$k$$$, an edge $$$e_i$$$ has exactly one common vertex with edge $$$e_{i-1}$$$ and exactly one common vertex with edge $$$e_{i+1}$$$ and these vertices are distinct (consider $$$e_0 = e_k$$$, $$$e_{k+1} = e_1$$$).

It is obvious that edges in a cycle-array form a cycle.

Let's define $$$f(e_1, e_2)$$$ as a function that takes edges $$$e_1$$$ and $$$e_2$$$ as parameters and returns the maximum between the weights of $$$e_1$$$ and $$$e_2$$$.

Let's say that we have a cycle-array $$$C = [e_1, e_2, \ldots, e_k]$$$. Let's define the price of a cycle-array as the sum of $$$f(e_i, e_{i+1})$$$ for all $$$i$$$ from $$$1$$$ to $$$k$$$ (consider $$$e_{k+1} = e_1$$$).

Let's define a cycle-split of a graph as a set of non-intersecting cycle-arrays, such that the union of them contains all of the edges of the graph. Let's define the price of a cycle-split as the sum of prices of the arrays that belong to it.

There might be many possible cycle-splits of a graph. Given a graph, your task is to find the cycle-split with the minimum price and print the price of it.

The first line contains one integer $$$n$$$ ($$$3 \le n\le 999$$$, $$$n$$$ is odd) — the number of nodes in the graph.

Each of the following $$$\frac{n \cdot (n-1)}{2}$$$ lines contain three space-separated integers $$$u$$$, $$$v$$$ and $$$w$$$ ($$$1 \le u,v \le n,u \neq v, 1 \le w \le 10^9$$$), meaning that there is an edge between the nodes $$$u$$$ and $$$v$$$ that has weight $$$w$$$.

Print one integer — the minimum possible price of a cycle-split of the graph.

3
1 2 1
2 3 1
3 1 1

3

5
4 5 4
1 3 4
1 2 4
3 2 3
3 5 2
1 4 3
4 2 2
1 5 4
5 2 4
3 4 2

35

Let's enumerate each edge in the same way as they appear in the input. I will use $$$e_i$$$ to represent the edge that appears $$$i$$$-th in the input.

The only possible cycle-split in the first sample 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$$$.

The optimal cycle-split in the second sample is $$$S = \{[e_3,e_8,e_9], [e_2,e_4,e_7,e_{10},e_5,e_1,e_6]\}$$$. The price of $$$[e_3,e_8,e_9]$$$ is equal to $$$12$$$, the price of $$$[e_2,e_4,e_7,e_{10},e_5,e_1,e_6]$$$ is equal to $$$23$$$, thus the price of the split is equal to $$$35$$$.