RailwayMaster
SRM 788 · 2020-07-22 · by square1001
Problem Statement
Alice lives in a city which has N stations. The stations are numbered 0, 1, 2, ..., N-1. In this city there are M railways, numbered 0, 1, 2, ..., M-1.
Each railway connects two stations. More precisely, railway i connects station a[i] and station b[i] bidirectionally. The value of railway i is v[i] dollars. (Each value is a positive integer.)
Initially, all citizens can travel from any station to any other station only by using some sequence of railways. When this condition is satisfied, we say that the city is connected.
Alice owns all M railways in this city. She is going to sell at most K railways. Her profit will be exactly the sum of values of the sold railways.
The sold railways will no longer be used for public transport. Alice must make sure that the city will remain connected after she sells the railways, otherwise she would get attacked by unhappy citizens.
What is the biggest profit (in dollars) Alice can earn without getting attacked?
Notes
- There can be two or more railways which connect the same pair of stations.
Constraints
- N will be between 2 and 101, inclusive.
- M will be between 1 and 100, inclusive.
- K will be between 1 and M, inclusive.
- The length of arrays a, b, and v will all be exactly M.
- a[i] and b[i] will be different numbers, both between 0 and N-1, inclusive.
- v[i] will be between 1 and 10000000 (10 million).
- The given railway network will be connected.
3
3
3
{0, 1, 2}
{1, 2, 0}
{224, 258, 239}
Returns: 258
In this example, the city has N = 3 station and the shape of railway is triangular. Here, if Alice sell road 1 which connects station 1 and 2, she can gain 258 dollars. She can sell at most K = 3 railways, however, if she sells more than one railway, the city will not be connected, and the citizens would attack. That's why she cannot gain more than 258 dollars, and you should return 258.
4
6
2
{0, 0, 0, 1, 1, 2}
{1, 2, 3, 2, 3, 3}
{500, 900, 600, 700, 800, 100}
Returns: 1700
In this example, there are N = 4 stations, and there is one road between every pair of stations. Alice can sell at most 2 railways. The best plan for Alice to sell railway 1 and 4. She will get 900 + 800 = 1700 dollars, and the city will still be connected.
5
7
1
{0, 1, 2, 3, 3, 0, 1}
{1, 2, 3, 4, 0, 2, 3}
{100, 100, 100, 900, 100, 100, 100}
Returns: 100
In this example, Alice cannot sell railway 3, because, if sold, the railway network will not be connected. It is possible to sell one of the other 6 railways. Whichever railway Alice chooses to sell among them, her profit will be 100 dollars.
5
7
3
{0, 0, 0, 0, 1, 2, 3}
{1, 1, 1, 1, 2, 3, 4}
{926, 815, 777, 946, 928, 634, 999}
Returns: 2687
It is possible that there are multiple railways between a pair of stations. In this example, it is optimal for Alice to sell railway 0, 1, and 3. Her profit will be 926 + 815 + 946 = 2687.
5
7
6
{0, 1, 2, 3, 4, 1, 3}
{1, 2, 3, 4, 0, 4, 0}
{118, 124, 356, 480, 625, 767, 911}
Returns: 2303
In this example, Alice's optimal solution is to sell railway 4, 5, and 6. Her profit will be 625 + 767 + 911 = 2303.
Submissions are judged against all 52 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RailwayMaster with a public method int maxProfit(int N, int M, int K, vector<int> a, vector<int> b, vector<int> v) · 52 test cases · 2 s / 256 MB per case