BuildersCountry

SRM 432 · 2009-01-06 · by nika

SRM 432 · 2009-01-06 · by nika · Graph Theory

Show categories

Class Name: BuildersCountry

Return Type: long

Method Name: minCost

Arg Types: (vector<int>, vector<int>, vector<int>, vector<string>, int)

Problem Statement

There's a far away country where only builders live. They have built a number of cities already, and some of them are connected with bidirectional roads. The existing roads are given in the String[] g, where the j-th character of the i-th element is 'Y' if there's a bidirectional road connecting cities i and j, and 'N' otherwise. Each city contains a number of houses, given in the int[] before, where the i-th element is the number of houses in city i. Exactly one builder lives in each house.

The country will go through a two-phase building process. In the first phase, new bidirectional roads will be built so that every pair of cities will be connected by some path. When a road is built between two cities, every builder from both cities will be involved and each builder will be paid roadCost units of money.

In the second phase, new houses will be built. You are given a int[] after, where the i-th element is the number of houses that must exist in city i after this phase is complete. In other words, after[i] - before[i] new houses must be built in city i during this phase. When a house is built, all builders in that city and all its neighboring cities will be involved and each one will be paid houseCost[i] units of money. Two cities are neighboring if they are directly connected by a road. After each house is built, a new builder will immediately live in that house. Houses can be built in any order.

Return the minimal possible cost required to finish both phases of the building process.

Constraints

before will contain between 1 and 50 elements, inclusive.
Each element of before will be between 1 and 100000, inclusive.
after will contain the same number of elements as before.
The i-th element of after will be between the i-th element of before and 100000, inclusive.
houseCost will contain the same number of elements as before.
Each element of houseCost will be between 1 and 100000, inclusive.
g will contain the same number of elements as before.
Each element of g will contain exactly n characters, where n is the number of elements in g.
Each element of g will contain only uppercase letters 'Y' and 'N'.
The i-th character of the i-th element of g will always be 'N'.
The i-th character of the j-th element of g will always be equal to the j-th character of the i-th element of g.
roadCost will be between 1 and 100000, inclusive.

Examples

{2, 1, 3, 5}
{2, 1, 3, 5}
{4, 5, 3, 2}
{"NNNN", "NNNN", "NNNN", "NNNN"}
1000
Returns: 13000

We can build roads from city 1 to all other cities for a total cost (1+2)*1000 + (1+3)*1000 + (1+5)*1000 = 13000. All houses are already built.

{1, 1, 1, 1}
{1, 3, 1, 2}
{8, 5, 3, 2}
{"NYNN", "YNYN", "NYNY", "NNYN"}
100000
Returns: 39

We don't need to add any roads. If we build one house in city 1, we need to pay 5*(1+1+1). After that, build one house in city 3 for a cost of 2*(1+1). Then, build another house in city 1. This time, the cost will be 5*(1+2+1) since 2 workers now live in city 1. The total cost is 15+4+20=39.

{9, 11}
{10, 11}
{5, 1}
{"NN", "NN"}
15
Returns: 400

Build one road and build one house.

{1}
{1000}
{2}
{"N"}
888
Returns: 999000

Build 999 houses. Total cost is (1+2+...+999)*2 = 999000.

{99, 23, 44, 55, 32}
{99, 23, 44, 55, 32}
{39, 32, 11, 23, 89}
{"NYNNN", "YNNNY", "NNNYY", "NNYNY", "NYYYN"}
54
Returns: 0

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

Coding Area

Language: C++17 · define a public class BuildersCountry with a public method long long minCost(vector<int> before, vector<int> after, vector<int> houseCost, vector<string> g, int roadCost) · 91 test cases · 2 s / 256 MB per case