TreeAndCycle
SRM 693 · 2016-06-04 · by jcvb
SRM 693 · 2016-06-04 · by jcvb · Dynamic Programming, Graph Theory
Problem Statement
Problem Statement
You are given an undirected tree with n vertices numbered 0 through n-1.
For each i between 0 and n-2, inclusive, the vertices (i+1) and pre[i] are connected by an edge.
We ensure pre[i] < i+1, so the edges are guaranteed to form a tree.
A cycle graph is an undirected graph with n vertices and n edges in which the edges form a single cycle through all vertices. Formally, a graph with n vertices and n edges is a cycle graph if there exists a permutation p[0], p[1],..., p[n-1] of its vertices such that the n edges are the edges (p[0],p[1]), (p[1],p[2]), (p[2],p[3]), ..., (p[n-2],p[n-1]), and (p[n-1],p[0]).
You want to transform the given tree into an arbitrary cycle graph by adding and/or removing edges. Removing the edge (i+1,pre[i]) costs costE[i]. Each vertex x has an associated weight costV[x]. The cost of adding a new edge (x,y) is costV[x]+costV[y]. The edges added in this way cannot be removed. Note that all the edges are undirected.
You are given the followingint[] s:
A cycle graph is an undirected graph with n vertices and n edges in which the edges form a single cycle through all vertices. Formally, a graph with n vertices and n edges is a cycle graph if there exists a permutation p[0], p[1],..., p[n-1] of its vertices such that the n edges are the edges (p[0],p[1]), (p[1],p[2]), (p[2],p[3]), ..., (p[n-2],p[n-1]), and (p[n-1],p[0]).
You want to transform the given tree into an arbitrary cycle graph by adding and/or removing edges. Removing the edge (i+1,pre[i]) costs costE[i]. Each vertex x has an associated weight costV[x]. The cost of adding a new edge (x,y) is costV[x]+costV[y]. The edges added in this way cannot be removed. Note that all the edges are undirected.
You are given the following
- The
int[] costV with n elements that contains the weight of each vertex. Remember that these weights are used to compute the costs of adding new edges. - The
int[] pre with n-1 elements that describes the shape of the tree. - The
int[] costE with n-1 elements: the costs of removing the edges described by pre.
Constraints
- n will be between 3 and 100, inclusive.
- costV will contain exactly n elements.
- pre will contain exactly n-1 elements.
- For each valid i, 0 <= pre[i] < i+1 holds.
- costE will contain exactly n-1 elements.
- Elements of costV and costE will be between 1 and 10,000, inclusive.
Examples
0)
{7,2,5,8}
{0,1,2}
{6,4,3}
Returns: 15
This graph is a path with edges (0,1),(1,2),(2,3). An optimal solution is to add edge (0,3) to make it a cycle. The cost is costV[0] + costV[3] = 15.
1)
{100,5,9,8}
{0,0,0}
{6,2,2}
Returns: 32
An optimal solution is to remove edge (0,3), and add edges (1,3), (2,3).
2)
{10,20,30,40,50,60,70,80,90}
{0,1,2,2,3,4,5,7}
{5,15,25,35,45,55,65,75}
Returns: 205
3)
{9658,9988,9998,9220,9367,9984,9984,9998,9994,9976,9482,9924,9992,9998,9997,9832,9402,9431,7643,9993,7396,9779,9942,9982,9809,9964,9991,9919,9998,9629,9995,9924,9998,9914,9996,9870,9998,9997,9990,9430,9987,9998,9989,9860,9962,9836,8097,9888,9998,9994,8922,9190,9832,9973,9979,9998,9781,9992,9976,9895,9991,9990,9984,8837,9996,9998,9997,8599,9483,9997,9955,9997,9674,9994,9196,9637,9953,9990,9981,9777,9939,9792,9981,9965,9946,9991,9247,9988,9988,9995,9993,9911,9955,9397,9995,8282,9998,9997}
{0,1,2,1,4,3,6,2,5,5,7,5,1,0,12,5,2,12,4,6,17,2,7,7,9,25,2,3,8,8,26,26,8,3,11,6,35,21,10,11,36,39,4,6,15,28,21,28,27,29,48,27,49,27,3,13,34,47,42,41,52,4,62,46,57,1,56,5,30,34,48,31,39,17,2,3,19,19,52,16,9,72,26,66,35,67,69,25,46,75,62,23,71,38,67,4,35}
{9600,9910,9087,9897,9945,9939,9965,9951,9996,9949,9984,9612,9925,9997,9998,9961,9998,9992,9997,9969,9888,9998,9998,9929,9780,9869,9998,9998,9996,9803,9996,9992,9941,9985,8613,9917,9990,8207,8400,9944,9998,9971,9998,9920,8907,9991,9992,9976,9895,7377,9995,8627,9997,9899,9994,8781,7138,9107,9982,9967,9927,9636,9973,9960,9464,9934,9992,9998,9992,9990,9583,9996,9933,9990,9797,9996,9992,9997,9647,8831,7658,9763,8459,8983,9998,9961,9993,9993,9323,9963,8782,9538,9871,8912,8840,9990,9927}
Returns: 886199
4)
{9984,8708,8276,9922,9994,8938,9991,9984,9609,9973,9998,9833,9592,9813,9978,9977,9836,9998,9998,9591,9794,9995,9673,9917,9980,9159,9951,9960,9062,9998,9463,9992,9992,9962,9784,9998,9702,7611,7666,9991,9672,9888,8763,9994,9994,9431,9998,9814,7878,9833,9871,9809,9978,9894,9709,9996,8468,9819,9975,9968,9383,9983,9998,9987,9985,8360,8618,9677,9936,9998,9743,9998,9927,9799,9985,9998,9176,9996,9986,9088,9997,9996,9972,9981,9554,9957,9993,9998,9998,9997,9965,9314,9994,9983,9976,9996,7092,9998,9997}
{0,1,0,2,3,5,5,3,8,9,2,5,0,5,12,9,16,2,0,1,12,6,17,16,6,22,5,6,2,23,22,20,25,29,26,11,24,7,21,9,27,2,4,37,28,8,21,36,10,41,34,16,50,29,50,16,14,13,14,40,41,56,6,42,20,6,7,37,49,42,22,69,23,12,8,67,41,44,20,71,31,5,20,75,35,47,29,58,73,6,53,12,21,31,55,27,28,91}
{1,15,4,10,1,99,9,197,2,87,1,59,118,4,3,1,170,3,13,1,209,162,78,3,1,69,2,12,1,5,3,6,17,68,3,107,33,1,259,55,31,112,2,18,15,84,1,1,63,151,36,71,2,2,1,3,4,17,1,1,2,43,5,154,2,13,214,272,6,6,2,14,6,277,23,3,13,1,5,1,1,13,6,36,1,1,9,1,11,2,30,203,1,254,45,98,1,2}
Returns: 634253
Submissions are judged against all 112 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TreeAndCycle with a public method int minimize(vector<int> costV, vector<int> pre, vector<int> costE) · 112 test cases · 2 s / 256 MB per case