道路的最大总重要性

2285. 道路的最大总重要性

给你一个整数 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
没有重复道路。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: long long maximumImportance(int n, vector<vector<int>>& roads) { } };

java 解法, 执行用时: 6 ms, 内存消耗: 63 MB, 提交时间: 2022-12-06 13:22:20

class Solution {
    public long maximumImportance(int n, int[][] roads) {
		long[] map = new long[n];//map[i] 表示第i少条路的城市有多少条路（后面的排序后表示的意思）
		for (int i = 0; i < roads.length; i++) {
			map[roads[i][0]]++;
			map[roads[i][1]]++;
		}
		int num=1;//城市数值 
		Arrays.sort(map);//将这些城市按有道路数从小到大排序
		long ans = 0L;
		for (int i = 0; i < map.length; i++) {
			ans+=map[i]*num;//道路重要性之和为==》   城市数值 *城市的道路数  
			num++;
		}
		return ans;
	}
}

golang 解法, 执行用时: 196 ms, 内存消耗: 12.6 MB, 提交时间: 2022-12-06 13:21:54

func maximumImportance(n int, roads [][]int) (ans int64) {
	deg := make([]int, n)
	for _, r := range roads {
		deg[r[0]]++
		deg[r[1]]++
	}
	sort.Ints(deg)
	for i, d := range deg {
		ans += int64(d) * int64(i+1)
	}
	return
}

python3 解法, 执行用时: 164 ms, 内存消耗: 30.3 MB, 提交时间: 2022-12-06 13:21:26

class Solution:
    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
        deg = [0] * n
        for x, y in roads:
            deg[x] += 1
            deg[y] += 1
        deg.sort()
        return sum(d * i for i, d in enumerate(deg, 1))

上一题

下一题

详情