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

给城市配 1 到 n 的值，让所有路的重要性之和最大

有 n 座城市，编号 0 到 n−1，还有若干条双向道路。你要给每座城市分一个 1 到 n 的整数，每个值只用一次。一条路的重要性是它连的两座城市值相加；所有路的重要性加起来，最大能到多少。题面例子 n=5、六条路 roads=[[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]，最优分配下答案是 43。

值有 n 的阶乘种排法，一种种试根本试不完

1 到 n 分给 n 座城市，排法有 n 的阶乘种，n 到五万量级根本没法枚举；何况每换一种分配都要把每条路重加一遍。这条路走不通。可总和是每座城市的值被反复加出来的。

一座城市的值，被它每条路各加进总和一次

别盯着路，盯着城市。某座城市分到的值，会被它连的每一条路各拿去加一次。它连了几条路，这个数叫它的度数，那它的值就在总和里出现几次。于是一座城市的贡献，就是它的值乘度数；整个答案就是所有城市「值 × 度数」之和。

剩下就是把 1 到 n 分下去、让这个乘积和最大。答案是大值配大度数：度数大的城市，值被加进总和更多次，理应拿最大值。这就是排序不等式——两组数两两相乘再求和，大的配大的、小的配小的，总和才最大，配反了只会变小。

数度数、升序排、第 i 位配上值 i

落到代码就三步。先开一个长度 n 的数组记度数，扫一遍路，每条路给它的两个端点各加 1。再把这排度数从小到大排好，最右就是最大度数。最后从左往右走，第 1 个位置配值 1、第 2 个配值 2，直到第 n 个配值 n，把每个「度数 × 该值」累加就是答案。

这步不必真记哪座城市分到几——排好序的度数逐位乘上 1 到 n 求和，就已经等价于大值配大度数。

n=5 那六条路，43 是怎么一位位加出来的

先数度数：六条路各给两端加 1，数完按城市编号排是 [2,3,4,2,1]——城 2 连四条最多，城 1 连三条，城 0 和城 3 各两条，城 4 只一条。

把这排度数升序排好，变成 [1,2,2,3,4]。从左往右配值：第 1 位度数 1 配值 1，1 × 1 = 1；第 2 位度数 2 配值 2，2 × 2 = 4；第 3 位度数 2 配值 3，3 × 2 = 6；第 4 位度数 3 配值 4，4 × 3 = 12；第 5 位度数 4 配值 5，5 × 4 = 20。五份贡献 1 + 4 + 6 + 12 + 20 加起来是 43。

复杂度只有排序那一项，坑全在整型和边界上

数度数扫一遍路是 O(m)，m 是路的条数；排序 n 个度数是 O(n log n)；累加是 O(n)。主导项是排序，整体 O(m + n log n)，空间 O(n)，就是度数数组。

真正容易出事的不是算法，是溢出：n 和度数都能到五万量级，值乘度数再累加会顶破 32 位整数，C++ 和 Java 得用 long long 或 long 存和、乘法先转长整型，Python 的整数没有上限不受影响。几个小边界顺带核一遍：两座城一条路，度数 [1,1] 配值 1、2 得 3；三座城连成三角，度数全是 2、配值 1 到 3 得 2 + 4 + 6 = 12；例二答案 20 同样能验出来。

Python

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))

C++

#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;
    }
};

Java

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;
    }
}