道路的最大总重要性 图解题解

这道题到底在问什么

输入

n=5, roads=[[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]

输出

43

输入

n=5, roads=[[0,3],[2,4],[1,3]]

输出

20

最优解：一步一步想明白

1. 3记牢这条主线:一座城市的贡献是它的值乘以它的度数。想让总贡献最大,就让度数大的城市拿大值。所以先数度数,再从小到大排,让排在越后面度数越大的城市,拿到越大的值。下面先在图上把度数数出来。
2. 4先数每座城市连了几条路(度数)舞台上是 5 座城市,编号 0 到 4,城市之间的连线就是双向道路。第一步和值多大没关系,先把每座城市的度数数出来,也就是它连了几条路。开始时每座城市旁边的度数都标着 0,接下来一条一条路地扫,给这条路的两个端点各加 1。
3. 5这条路连着城 0 和城 1,准备给两头各加 1看第 1 条路 [0, 1]。高亮的就是眼下这条路,它连着城 0 和城 1。数度数很机械,一条路给它的两个端点各记一笔,先不管这两座城市将来分到多大的值。
4. 6城 0:1,城 1:1两头各加 1:城 0 的度数变成 1,城 1 的度数变成 1。度数谁高谁低先别急着下结论,扫到一半的中间态容易看走眼,等 6 条路全数完再一起比,才知道谁是最忙的枢纽。
5. 7这条路连着城 1 和城 2,准备给两头各加 1看第 2 条路 [1, 2]。高亮的就是眼下这条路,它连着城 1 和城 2。数度数很机械,一条路给它的两个端点各记一笔,先不管这两座城市将来分到多大的值。
6. 8城 1:2,城 2:1两头各加 1:城 1 的度数变成 2,城 2 的度数变成 1。度数谁高谁低先别急着下结论,扫到一半的中间态容易看走眼,等 6 条路全数完再一起比,才知道谁是最忙的枢纽。
7. 9这条路连着城 2 和城 3,准备给两头各加 1看第 3 条路 [2, 3]。高亮的就是眼下这条路,它连着城 2 和城 3。数度数很机械,一条路给它的两个端点各记一笔,先不管这两座城市将来分到多大的值。
8. 10城 2:2,城 3:1两头各加 1:城 2 的度数变成 2,城 3 的度数变成 1。度数谁高谁低先别急着下结论,扫到一半的中间态容易看走眼,等 6 条路全数完再一起比,才知道谁是最忙的枢纽。
9. 11这条路连着城 0 和城 2,准备给两头各加 1看第 4 条路 [0, 2]。高亮的就是眼下这条路,它连着城 0 和城 2。数度数很机械,一条路给它的两个端点各记一笔,先不管这两座城市将来分到多大的值。
10. 12城 0:2,城 2:3两头各加 1:城 0 的度数变成 2,城 2 的度数变成 3。度数谁高谁低先别急着下结论,扫到一半的中间态容易看走眼,等 6 条路全数完再一起比,才知道谁是最忙的枢纽。
11. 13这条路连着城 1 和城 3,准备给两头各加 1看第 5 条路 [1, 3]。高亮的就是眼下这条路,它连着城 1 和城 3。数度数很机械,一条路给它的两个端点各记一笔,先不管这两座城市将来分到多大的值。
12. 14城 1:3,城 3:2两头各加 1:城 1 的度数变成 3,城 3 的度数变成 2。度数谁高谁低先别急着下结论,扫到一半的中间态容易看走眼,等 6 条路全数完再一起比,才知道谁是最忙的枢纽。
13. 15这条路连着城 2 和城 4,准备给两头各加 1看第 6 条路 [2, 4]。高亮的就是眼下这条路,它连着城 2 和城 4。数度数很机械,一条路给它的两个端点各记一笔,先不管这两座城市将来分到多大的值。
14. 16城 2:4,城 4:1两头各加 1:城 2 的度数变成 4,城 4 的度数变成 1。度数谁高谁低先别急着下结论,扫到一半的中间态容易看走眼,等 6 条路全数完再一起比,才知道谁是最忙的枢纽。
15. 17城 2 度数 4 最大,城 4 度数 1 最小6 条路全数完了。按城市编号排,度数是 [2, 3, 4, 2, 1]:城 2 连了 4 条路最多,城 1 连 3 条,城 0 和城 3 各连 2 条,城 4 只连 1 条最少。度数一出来,谁该拿大值就清楚了:城 2 该拿最大的 5,城 4 拿最小的 1。下面把这些度数排个序,让分配一目了然。
16. 18还没排序,顺序是城 0 到城 4 的度数把刚才每座城市的度数抄成一排,从左到右是城 0 到城 4,值分别是 2、3、4、2、1。现在它是乱的,不方便配值。下一步把它从小到大排好,这样越靠右度数越大,正好对应越大的值。
17. 19从小到大:最小度数在最左,最大在最右排好序,现在是 [1, 2, 2, 3, 4]。最左边是最小的度数 1,最右边是最大的度数 4。接下来从左往右走,第 1 个位置配值 1,第 2 个配值 2,一直到第 5 个配值 5。位置越靠右度数越大,拿到的值也越大,这就把大值稳稳配给了大度数。
18. 20贡献 = 值 1 × 度数 1 = 1走到第 1 个位置,这里度数是 1,按规矩配上值 1。这座城市的贡献就是值乘度数,1 × 1 = 1。把它加进累计和,累计从 0 变成 1。继续往右,度数更大的位置会配更大的值。
19. 21贡献 = 值 2 × 度数 2 = 4走到第 2 个位置,这里度数是 2,按规矩配上值 2。这座城市的贡献就是值乘度数,2 × 2 = 4。把它加进累计和,累计从 1 变成 5。继续往右,度数更大的位置会配更大的值。
20. 22贡献 = 值 3 × 度数 2 = 6走到第 3 个位置,这里度数是 2,按规矩配上值 3。这座城市的贡献就是值乘度数,3 × 2 = 6。把它加进累计和,累计从 5 变成 11。继续往右,度数更大的位置会配更大的值。
21. 23贡献 = 值 4 × 度数 3 = 12走到第 4 个位置,这里度数是 3,按规矩配上值 4。这座城市的贡献就是值乘度数,4 × 3 = 12。把它加进累计和,累计从 11 变成 23。继续往右,度数更大的位置会配更大的值。
22. 24贡献 = 值 5 × 度数 4 = 20走到第 5 个位置,这里度数是 4,按规矩配上值 5。这座城市的贡献就是值乘度数,5 × 4 = 20。把它加进累计和,累计从 23 变成 43。这是最大的度数配上了最大的值,贡献也最大。
23. 25各位贡献相加 = 43五个位置全配完了。把每位的贡献 1 + 4 + 6 + 12 + 20 加起来,正好是 43。这就是最优分配下所有道路重要性之和的最大值。回头看,大值都落在了度数大的城市上,一分值也没浪费在冷清的城市上,这就是排序不等式给的最优安排。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
        deg = [0] * n
        for a, b in roads:
            deg[a] += 1
            deg[b] += 1
        deg.sort()
        return sum(i * v for i, v in enumerate(deg, 1))

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    long long maximumImportance(int n, vector<vector<int>>& roads) {
        vector<int> deg(n);
        for (auto& r : roads) {
            ++deg[r[0]];
            ++deg[r[1]];
        }
        sort(deg.begin(), deg.end());
        long long ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += (i + 1LL) * deg[i];
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public long maximumImportance(int n, int[][] roads) {
        int[] deg = new int[n];
        for (int[] r : roads) {
            ++deg[r[0]];
            ++deg[r[1]];
        }
        Arrays.sort(deg);
        long ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += (long) (i + 1) * deg[i];
        }
        return ans;
    }
}

复杂度

面试官可能追问