Problem Statement | | |
Cat Noku received an undirected, connected, weighted graph with n nodes and m edges.
The edges are labeled from 0 to m-1, and are described by the int[]s a, b, w.
The i-th edge connects the a[i]-th node to the b[i]-th node with weight w[i].
It is guaranteed that this graph is connected.
Also, it is guaranteed that this graph has no self-loops or multiple edges.
Cat Noku also has two spanning trees of the graph.
These are described the int[]s m1, m2, which each contain exactly n-1 elements.
The elements of each of these int[]s are the indices of the edges that form one of the two spanning trees.
Note that it is possible for these two spanning trees to have some (possibly even all) edges in common.
Cat Noku would like to make his spanning trees extreme.
More specifically, he wants the following:
- The spanning tree described by m1 is a minimum spanning tree.
- The spanning tree described by m2 is a maximum spanning tree.
Of course, the conditions may not be currently satisfied, so to fix this, Cat Noku can modify the edge weights.
In each second, he can choose exactly one edge, and either increase or decrease its weight by 1.
All edge weights must remain positive at all times.
Please help Cat Noku find the minimum number of seconds needed to satisfy his goal.
| | | Definition | | | | Class: | ExtremeSpanningTrees | | Method: | minTime | | Parameters: | int[], int[], int[], int[], int[] | | Returns: | long | | Method signature: | long minTime(int[] a, int[] b, int[] w, int[] m1, int[] m2) | | (be sure your method is public) |
| | | | | | Notes | | - | - A minimum spanning tree is a spanning tree that has the smallest sum of edge weights among all spanning trees. A maximum spanning tree is defined in the same way. | | | Constraints | | - | n will be between 2 and 50, inclusive. | | - | m will be between n-1 and 1,000, inclusive. | | - | a,b,w will each contain exactly m elements. | | - | Each element of w will be between 1 and 10^9, inclusive. | | - | Each element of a,b will be between 0 and n-1, inclusive. | | - | The edges described (a[i], b[i]) will describe a simple undirected connected graph. | | - | m1,m2 will each contain exactly n-1 elements. | | - | Elements in m1 will be distinct, and between 0 and m-1, inclusive. | | - | Elements in m2 will be distinct, and between 0 and m-1, inclusive. | | - | The indices specified by m1 will denote a spanning tree. | | - | The indices specified by m2 will denote a spanning tree. | | | Examples | | 0) | | | | {0,1,2,3,4} | {1,2,3,4,0} | {6,1,2,4,9} | {1,0,3,2} | {3,1,2,0} |
| Returns: 12 | | In this case, the same tree must be both a minimum and a maximum spanning tree. It is optimal to make all edge weights equal, which means we should move the edge weights to the median weight (in this case 4). Thus, the answer is |6-4|+|1-4|+|2-4|+|4-4|+|9-4| = 12. |
|
| | 1) | | | | {0,1,2,3,4} | {1,2,3,4,0} | {1000000000, 1, 50000, 230, 78778878} | {1,2,3,4} | {0,1,2,4} |
| Returns: 229 | | One optimal solution in this case is to increase the weight on the edge labeled 1 to 230. |
|
| | 2) | | | | {2, 3, 2, 1, 4, 3, 1, 2} | {4, 0, 1, 0, 0, 4, 3, 0} | {35, 69, 83, 48, 23, 77, 18, 75} | {7, 2, 4, 6} | {6, 0, 3, 5} |
| Returns: 126 | |
| | 3) | | | | {18, 10, 7, 20, 25, 16, 0, 25, 1, 1, 18, 5, 21, 29, 0,
19, 27, 5, 5, 2, 5, 14, 24, 28, 17, 17, 13, 28, 29, 21,
27, 14, 3, 4, 0, 6, 7, 2, 19, 22, 1, 15, 28, 28, 22, 4,
18, 27, 25, 25, 16, 26, 14, 24, 28, 23, 23, 2, 7, 25, 27,
28, 24, 21, 3, 1, 4, 4, 23, 21}
| {26, 1, 0, 25, 6, 7, 19, 10, 3, 25, 19, 28, 24, 10, 10,
1, 4, 21, 2, 13, 11, 9, 23, 27, 22, 25, 16, 25, 3, 3, 23,
21, 20, 25, 5, 27, 12, 10, 10, 9, 13, 8, 22, 29, 16, 21,
0, 8, 8, 11, 20, 29, 13, 7, 20, 11, 5, 3, 6, 22, 2, 21,
16, 18, 0, 24, 2, 15, 16, 23} | {178550173, 70889251, 552583494, 693530287, 913018412,
813354729, 22559015, 790019960, 417638821, 350031148,
342183709, 546736964, 846258018, 288707281, 910585230,
217659326, 472037330, 407441317, 869355814, 510462471,
495766436, 645229822, 817030, 843038598, 814619628, 144969408,
832500308, 150645645, 400781547, 266132945, 112756643,
991866897, 166797713, 408918210, 192114032, 765168046,
69601053, 422959288, 206902656, 71012802, 520439340, 779668518,
457709439, 792537906, 212760134, 200551833, 511130875,
811123320, 772309593, 734005608, 802837429, 982498923,
335250225, 43356697,621725643, 161179558, 278880928, 88948197,
77554027, 686360474, 851408784, 777256397, 279272225, 856462366,
912791986, 518766837, 430982430, 985439708, 307712218, 659114756}
| {60, 44, 62, 66, 0, 34, 69, 1, 17, 40, 65, 6, 30, 21, 50, 8,
10, 37, 41, 23, 9, 39, 36, 35, 58, 48, 28, 24, 20} | {20, 12, 29, 23, 26, 10, 55, 58, 53, 40, 24, 50, 15, 11, 35,
48, 43, 63, 60, 39, 59, 46, 7, 42, 52, 41, 51, 36, 67} |
| Returns: 11341657393 | |
| | 4) | | | | |
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
|
