Author: | Anton Trygub |
Developer: | Stanislav Bezkorovainyi |
Editorialist: | Stanislav Bezkorovainyi |
Since is always odd, then the degree of each vertex (i.e number of vertices adjacent to it) is always even, so there are even number of edges adjacent to each vertex.
Let's look at an edge that connects two vertices (v_1, v_2). In a cycle-array to which will belong, this edge will be adjacent (i.e compared when calculating the price of the cycle-array) with exactly one edge, that is connected to v_1 and exactly one edge that is connected to v_2.
So, if we look at a vertex , then all the edges that are connected to it can be divided into \frac{n-1}{2} pairs of edges (e_1,e_2), where e_1 and e_2 belong to same cycle-array and e_1 is adjacent with e_2. So now, we can define the price of a vertex as the sum of maximums of weights in such pairs. In other words, if all the edges that are adjacent to a vertex are arranged in pairs like that (e_1, e_2), (e_3,e_4),\ldots,(e_{n-2}, e_{n-1}), then:
It is easy to see that sum of prices for all of the vertices is equal to price of the cycle-split.
Let's say that edges e_1,e_2,\ldots,e_{n-1} with weights w_1,w_2,\ldots,w_{n-1} are connected to . Let's say, that w' is a sorted array . It is easy to prove that the smallest possible price of a vertex can be obtained if we split the wieghts into pairs in the following way: (w'_1,w'_2), (w'_3,w'_4),\ldots,(w'_{n-2}, w'_{n-1}).
What is left to prove is that it is achievable. Let's say that for each vertex we arranged edges adjacent to it into pairs, such that the price of the vertex is smallest possible. Let's denote this arrangement as (e'_1, e'_2), (e'_3, e'_4), \ldots, (e'_{n-2}, e'_{n-1}). Let's call a pair (e'_i, e'_{i+1}) unfulfilled if e'_i was used and e'_{i+1} weren't or vice versa.
Now, we can build the necessary cycle-split the following way:
If all of the edges were used, then stop the algorithm.
Otherwise, we should start forming a new cycle-array that will be added to the split. Find any vertex that has an unused edge adjacent to it. We add this edge to the current cycle-array and mark it as used. Let's say that it is edge that connects vertex with vertex . Let's set our current vertex as and repeat the following algorithm:
Let's suppose that our current vertex is some vertex . If there are no unfulfilled pairs of it, then the cycle-array has been finally formed, thus we stop the algorithm.
Otherwise, there is exactly one unfulfilled pair. Wlog that it is pair (e'_{i}, e'_{i+1}).
If e'_{i} has not been used yet, then add it to our cycle-array and set the current vertex as a vertex that the edge e'_{i} connects with. Now there are no unfulfilled pairs of the vertex . It can be seen that e'_{i+1} was added just before we set as our current vertex. Thus, e'_{i} and e'_{i+1} will be compared, when calculating price of the array.
The similar works for the case when e'_{i+1} has not been fulfilled.
The cycle array that is obtained this way is always valid, because it is an Euler's tour of the edges that belong to it.
So now, we have proven the solution. How to find the answer?
For any vertex create an array w' that has all the weights of the edges that are connected to it in an ascending order. The price of this vertex is the sum of the values on even positions in the array w'. The price of the split is the sum of prices of all the vertices.
Total time complexity O(n^2 \log n).