BiconnectedDiv1
SRM 693 · 2016-06-04 · by jcvb
SRM 693 · 2016-06-04 · by jcvb · Dynamic Programming, Graph Theory, Greedy
Problem Statement
Problem Statement
A 2-edge-connected graph is a connected undirected graph with the following property:
for any two distinct vertices u,v and for any edge e there exists a path from u to v that does not contain e.
You are given a graph G with n vertices numbered 0 through n-1, where n is not less than 3. The graph has a very specific structure. For each i between 0 and n-2, inclusive, vertices i and i+1 are connected by an edge with weight w1[i]. Additionally, for each i between 0 and n-3, inclusive, vertices i and i+2 are connected by an edge with weight w2[i]. It is easy to verify that this graph is 2-edge-connected.
Note that some of the edge weights may be zeros. An edge with weight zero is still present in the graph, just like any other edge.
You may erase some edges of the graph G. If you do, you must do it in such a way that the graph remains 2-edge-connected. Your goal is to minimize the sum of weights of edges that remain in G.
You are given theint[] s w1 and w2 that describe the graph G.
Compute and return the smallest possible sum of weights of a graph that can be produced in the way described above.
You are given a graph G with n vertices numbered 0 through n-1, where n is not less than 3. The graph has a very specific structure. For each i between 0 and n-2, inclusive, vertices i and i+1 are connected by an edge with weight w1[i]. Additionally, for each i between 0 and n-3, inclusive, vertices i and i+2 are connected by an edge with weight w2[i]. It is easy to verify that this graph is 2-edge-connected.
Note that some of the edge weights may be zeros. An edge with weight zero is still present in the graph, just like any other edge.
You may erase some edges of the graph G. If you do, you must do it in such a way that the graph remains 2-edge-connected. Your goal is to minimize the sum of weights of edges that remain in G.
You are given the
Constraints
- n will be between 3 and 100, inclusive.
- w1 will contain exactly n-1 elements.
- w2 will contain exactly n-2 elements.
- Each element of w1 and w2 will be between 0 and 10,000, inclusive.
Examples
0)
{1,2}
{3}
Returns: 6
There are three vertices and three edges (0,1), (1,2), (2,0). If you erase edge (0,1), then any path from 0 to 1 has to go through edge (0,2). And if you erase two or more edges, the graph will become disconnected. So you cannot erase anything.
1)
{3,0,4}
{1,2}
Returns: 10
An optimal solution is to keep all the edges.
2)
{3,3,3,3}
{3,6,3}
Returns: 18
An optimal solution is to erase edge (1,3).
3)
{7243,7525,8467,6351,9453,8456,8175,5874,6869,7400,6438,8926,6876}
{2642,1743,3546,4100,2788,3019,2678,1935,1790,2674,3775,1920}
Returns: 46729
4)
{0,0,0}
{0,0}
Returns: 0
Submissions are judged against all 147 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BiconnectedDiv1 with a public method int minimize(vector<int> w1, vector<int> w2) · 147 test cases · 2 s / 256 MB per case