道路的最大总重要性

难度: Medium

给你一个整数 n ，表示一个国家里的城市数目。城市编号为 0 到 n - 1 。

给你一个二维整数数组 roads ，其中 roads[i] = [a_i, b_i] 表示城市 a_i 和 b_i 之间有一条双向道路。

你需要给每个城市安排一个从 1 到 n 之间的整数值，且每个值只能被使用一次。道路的 重要性 定义为这条道路连接的两座城市数值之和。

请你返回在最优安排下，所有道路重要性 之和最大为多少。

示例 1：

输入：n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
输出：43
解释：上图展示了国家图和每个城市被安排的值 [2,4,5,3,1] 。
- 道路 (0,1) 重要性为 2 + 4 = 6 。
- 道路 (1,2) 重要性为 4 + 5 = 9 。
- 道路 (2,3) 重要性为 5 + 3 = 8 。
- 道路 (0,2) 重要性为 2 + 5 = 7 。
- 道路 (1,3) 重要性为 4 + 3 = 7 。
- 道路 (2,4) 重要性为 5 + 1 = 6 。
所有道路重要性之和为 6 + 9 + 8 + 7 + 7 + 6 = 43 。
可以证明，重要性之和不可能超过 43 。

示例 2：

输入：n = 5, roads = [[0,3],[2,4],[1,3]]
输出：20
解释：上图展示了国家图和每个城市被安排的值 [4,3,2,5,1] 。
- 道路 (0,3) 重要性为 4 + 5 = 9 。
- 道路 (2,4) 重要性为 2 + 1 = 3 。
- 道路 (1,3) 重要性为 3 + 5 = 8 。
所有道路重要性之和为 9 + 3 + 8 = 20 。
可以证明，重要性之和不可能超过 20 。

提示：

2 <= n <= 5 * 10⁴
1 <= roads.length <= 5 * 10⁴
roads[i].length == 2
0 <= a_i, b_i <= n - 1
a_i != b_i
没有重复道路。

Submission

运行时间: 106 ms

内存: 32.7 MB

class Solution:
    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
        feq = [0] * n
        for a, b in roads:
            feq[a] += 1
            feq[b] += 1
        feq.sort()
        res = 0
        for a, i in enumerate(feq, 1):
            res += a * i
        return res

Explain

本题的目标是为每个城市分配一个唯一的数值，以使得所有道路的重要性之和最大化。解题思路基于这样的观察：连接较多道路的城市应该被分配更大的数值，以最大化其贡献。首先，计算每个城市连接的道路数量，然后按这个数量对城市进行排序。城市的数值从小到大分配，即连接最少道路的城市分配最小的数值，连接最多道路的城市分配最大的数值。这样可以保证每条道路的两个城市的数值之和尽可能大。计算每个城市数值与其连接的道路数的乘积之和，得到最终的总重要性。

时间复杂度: O(n log n)

空间复杂度: O(n)

# 为每个城市分配一个唯一的数值以最大化所有道路的重要性之和
class Solution:
    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
        feq = [0] * n  # 计算每个城市连接的道路数
        for a, b in roads:  # 遍历所有道路，更新两个城市的连接数
            feq[a] += 1
            feq[b] += 1
        feq.sort()  # 对城市按连接的道路数量进行排序
        res = 0  # 初始化总重要性
        for a, i in enumerate(feq, 1):  # 分配数值，从1到n，计算总重要性
            res += a * i  # 城市的数值乘以连接的道路数
        return res  # 返回计算得到的总重要性

Explore

通过对每个城市连接的道路数进行排序，可以确保数值的分配顺序。在排序过程中，我们将连接道路数较少的城市放在前面，连接道路数较多的城市放在后面。然后，我们从1到n给这些城市分配数值，这样连接道路数较多的城市自然会被分配到较高的数值。这种方法通过排序来保证数值分配的顺序性和正确性。

在题解中，直接对连接道路数的数组进行排序，这种做法丢失了城市ID与其连接数的直接关联。为了保持索引与城市ID的关系，应该在排序前使用元组列表来存储城市ID与其连接数，例如[(城市ID, 连接数)]。排序时根据连接数进行排序，这样排序后的列表仍然保留了城市ID与连接数的正确对应关系。

如果所有城市的连接道路数量相同，那么不论如何分配数值，每条道路的重要性计算结果都是相同的。因此，在这种极端情况下，任何数值分配方法的结果都是等效的，该算法仍然有效，但优化的空间或影响是不存在的，因为所有配置方式导致的结果都一样。

算法在计算每个城市连接的道路数时确实考虑了道路的双向特性。每条道路由两个城市端点（a, b）组成，算法中通过对每个端点的连接数分别增加，确保了双向道路的每个方向都被计算了一次。这样，每条道路对每个端点城市的连接数贡献都是1，从而避免了重复计算。