17966번 - 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₁, e₂, . . . , 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₀ = e_k, e_k+1 = e₁).

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

Let’s define f(e₁, e₂) as a function that takes edges e₁ and e₂ as parameters and returns the maximum between the weights of e₁ and e₂.

Let’s say that we have a cycle-array C = [e₁, e₂, . . . , 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₁).

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 ≤ n ≤ 999, n is odd) — the number of nodes in the graph.

Each of the following n·(n−1)/2 lines contain three space-separated integers u, v and w (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ w ≤ 10⁹), 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.

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

The only possible cycle-split in the first sample is S = {[e₁, e₂, e₃]}. f(e₁, e₂)+f(e₂, e₃)+f(e₃, e1) = 1+1+1 = 3.

The optimal cycle-split in the second sample is S = {[e₃, e₈, e₉], [e₂, e₄, e₇, e₁₀, e₅, e₁, e₆]}. The price of [e₃, e₈, e₉] is equal to 12, the price of [e₂, e₄, e₇, e₁₀, e₅, e₁, e₆] is equal to 23, thus the price of the split is equal to 35.