Graph and Cycles#11283
There is an undirected weighted complete graph of vertices where is odd.
Let's define a cycle-array of size as an array of edges [e[1], e[2], ..., e[k]] that has the following properties:
is greater than .
For any from to , 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 (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 = [e[1], e[2], ..., e[k]]. Let's define the price of a cycle-array as the sum of (e[i], e[i+1]) for all from to (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 (3 \le n \le 999, is odd) - the number of nodes in the graph.
Each of the following n \cdot (n - 1) / 2 lines contain three space-separated integers , and (1 \le u, v \le n, u \neq v, 1 \le w \le 10^9), meaning that there is an edge between the nodes and that has weight .
Print one integer - the minimum possible price of a cycle-split of the graph.
Example 1
Example 2
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 -th in the input.
The only possible cycle-split in the first sample is = {[e[1], e[2], e[3]]}: (e[1], e[2]) + (e[2], e[3]) + (e[3], e[1]) = 1 + 1 + 1 = 3.
The optimal cycle-split in the second sample is = {[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 , the price of [e[2], e[4], e[7], e[10], e[5], e[1], e[6]] is equal to , thus the price of the split is equal to .