Connection Status:
Competition Arena > BearKRoads

BearKRoads

SRM 695 · 2016-06-25 · by Errichto

SRM 695 · 2016-06-25 · by Errichto · Brute Force
Class Name: BearKRoads
Return Type: int
Method Name: maxHappy
Arg Types: (vector<int>, vector<int>, vector<int>, int)
Problem Statement

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.

Notes

  • 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.

Constraints

    Examples
    0)
    {10, 50, 50, 10}
{0, 1, 2}
{1, 2, 3}
1
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.

    1)
    {10, 50, 50, 10}
{0, 1, 2}
{1, 2, 3}
2
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.

    2)
    {42, 100, 500}
{0, 1}
{1, 2}
2
Returns: 642

    We can renovate both roads. All 42 + 100 + 500 = 642 citizens will be happy.

    3)
    {42, 100, 500, 999, 999, 999, 999}
{0, 1}
{1, 2}
2
Returns: 642
    4)
    {969,467,808,263,179,428,595,557,406,80}
{5,4,9,7,9,3}
{4,0,8,8,0,1}
3
Returns: 2841

    Submissions are judged against all 101 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

    Coding Area

    Language: C++17 · define a public class BearKRoads with a public method int maxHappy(vector<int> x, vector<int> a, vector<int> b, int K) · 101 test cases · 2 s / 256 MB per case

    Submitting as anonymous