Challenge

Problem

Solutions

Submissions

Maximum Total Importance of Roads

Challenge Points: 20

Level: Medium

You are given an integer n, representing how many cities there are (numbered from 0 to n-1).
You also receive a list roads, where each element [a, b] means there is a two-way road between city a and city b.

Your task is to assign every city a unique number from 1 to n.
These assigned numbers represent "importance values".
The importance of a single road equals:

value_of_city_a + value_of_city_b

You must assign the values in such a way that the total importance of all roads becomes as large as possible.

Return that maximum possible total importance.

Example 1:

Input: n = 4 roads = [[0,1], [1,2], [2,3], [0,3]]

Output: 20

Explanation:

One optimal assignment: Cities → [3, 4, 2, 1] Road importance → (0,1) → 3 + 4 = 7 (1,2) → 4 + 2 = 6 (2,3) → 2 + 1 = 3 (0,3) → 3 + 1 = 4 Total = 22

Example 2:

Input: n = 3 roads = [[0,2], [1,2]]

Output: 9

Explanation:

Assignment: [2, 1, 3] Roads → 2+3 = 5, 1+3 = 4 Total = 9

to Continue

Accepted:

Submission:

Report an issue

Code

You need toto run or submitYou need toto run or submit

Test Case

Test Result