Get Time

   Problem Statement  

 Problem Statement for BearKRoads

Problem Statement


Bearland consists of N cities, numbered 0 through N-1. For each i, city i is inhabited by x[i] citizens. You are given the int[] x with N elements.

There are M bidirectional roads. Each road connects two different cities. No two roads connect the same pair of cities.

Do you know that feeling when your fridge is full and you still don't know what to eat (and you eventually order a pizza)? The citizens of Bearland have the same feeling whenever they have to choose from too many roads. Thus, the road network in Bearland was designed in such a way that every city is incident to at most three roads. In other words, each city is directly connected to at most three other cities.

You are given the description of the road network: the int[]s a and b with M elements each. For each valid i, there is a road that connects cities a[i] and b[i].

All roads in Bearland were built a long time ago and their current condition is quite bad. Limak, a public transport inspector, can choose a few of the existing roads and renovate them. You are given the int K: the maximum number of roads Limak can renovate.

After the renovation, each citizen will be happy if and only if at least one of the roads from their city was renovated. Find and return the maximum number of happy citizens.



Parameters:int[], int[], int[], int
Method signature:int maxHappy(int[] x, int[] a, int[] b, int K)
(be sure your method is public)


-N will be between 2 and 1000, inclusive.
-x will contain exactly N elements.
-Each element in x will be between 1 and 999, inclusive.
-M will be between 1 and 1000.
-a and b will each contain exactly M elements.
-Each element in a and in b will be between 0 and N-1, inclusive.
-No road will connect a city to itself.
-No two roads will connect the same pair of cities.
-Every city will be incident to at most three roads.
-K will be between 1 and 7, inclusive.
-K will not be greater than M.


{10, 50, 50, 10}
{0, 1, 2}
{1, 2, 3}
Returns: 100
There are four cities and three roads: 0-1, 1-2 and 2-3. We can only renovate at most one road. It is optimal to renovate the road 1-2. This makes 100 citizens happy.
{10, 50, 50, 10}
{0, 1, 2}
{1, 2, 3}
Returns: 120
This is the same country but now we have K=2. Now the optimal solution is to renovate the roads 0-1 and 2-3. This makes all 120 citizens happy.
{42, 100, 500}
{0, 1}
{1, 2}
Returns: 642
We can renovate both roads. All 42 + 100 + 500 = 642 citizens will be happy.
{42, 100, 500, 999, 999, 999, 999}
{0, 1}
{1, 2}
Returns: 642
Returns: 2841
Returns: 8
Returns: 9
Returns: 173

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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 695 Round 1 - Division I, Level Two