题目描述
思路解析动画文字版
记牢这条主线:一座城市的贡献是它的值乘以它的度数。想让总贡献最大,就让度数大的城市拿大值。所以先数度数,再从小到大排,让排在越后面度数越大的城市,拿到越大的值。下面先在图上把度数数出来。
初始 · 5 座城市,度数全为 0：舞台上是 5 座城市,编号 0 到 4,城市之间的连线就是双向道路。第一步和值多大没关系,先把每座城市的度数数出来,也就是它连了几条路。开始时每座城市旁边的度数都标着 0,接下来一条一条路地扫,给这条路的两个端点各加 1。
第 1 / 6 条路 · [0, 1]：看第 1 条路 [0, 1]。高亮的就是眼下这条路,它连着城 0 和城 1。数度数很机械,一条路给它的两个端点各记一笔,先不管这两座城市将来分到多大的值。
路 [0, 1] 数完 · 城 0 度数到 1,城 1 度数到 1：两头各加 1:城 0 的度数变成 1,城 1 的度数变成 1。度数谁高谁低先别急着下结论,扫到一半的中间态容易看走眼,等 6 条路全数完再一起比,才知道谁是最忙的枢纽。
第 2 / 6 条路 · [1, 2]：看第 2 条路 [1, 2]。高亮的就是眼下这条路,它连着城 1 和城 2。数度数很机械,一条路给它的两个端点各记一笔,先不管这两座城市将来分到多大的值。
路 [1, 2] 数完 · 城 1 度数到 2,城 2 度数到 1：两头各加 1:城 1 的度数变成 2,城 2 的度数变成 1。度数谁高谁低先别急着下结论,扫到一半的中间态容易看走眼,等 6 条路全数完再一起比,才知道谁是最忙的枢纽。
第 3 / 6 条路 · [2, 3]：看第 3 条路 [2, 3]。高亮的就是眼下这条路,它连着城 2 和城 3。数度数很机械,一条路给它的两个端点各记一笔,先不管这两座城市将来分到多大的值。
路 [2, 3] 数完 · 城 2 度数到 2,城 3 度数到 1：两头各加 1:城 2 的度数变成 2,城 3 的度数变成 1。度数谁高谁低先别急着下结论,扫到一半的中间态容易看走眼,等 6 条路全数完再一起比,才知道谁是最忙的枢纽。
第 4 / 6 条路 · [0, 2]：看第 4 条路 [0, 2]。高亮的就是眼下这条路,它连着城 0 和城 2。数度数很机械,一条路给它的两个端点各记一笔,先不管这两座城市将来分到多大的值。
路 [0, 2] 数完 · 城 0 度数到 2,城 2 度数到 3：两头各加 1:城 0 的度数变成 2,城 2 的度数变成 3。度数谁高谁低先别急着下结论,扫到一半的中间态容易看走眼,等 6 条路全数完再一起比,才知道谁是最忙的枢纽。
第 5 / 6 条路 · [1, 3]：看第 5 条路 [1, 3]。高亮的就是眼下这条路,它连着城 1 和城 3。数度数很机械,一条路给它的两个端点各记一笔,先不管这两座城市将来分到多大的值。
路 [1, 3] 数完 · 城 1 度数到 3,城 3 度数到 2：两头各加 1:城 1 的度数变成 3,城 3 的度数变成 2。度数谁高谁低先别急着下结论,扫到一半的中间态容易看走眼,等 6 条路全数完再一起比,才知道谁是最忙的枢纽。
第 6 / 6 条路 · [2, 4]：看第 6 条路 [2, 4]。高亮的就是眼下这条路,它连着城 2 和城 4。数度数很机械,一条路给它的两个端点各记一笔,先不管这两座城市将来分到多大的值。
路 [2, 4] 数完 · 城 2 度数到 4,城 4 度数到 1：两头各加 1:城 2 的度数变成 4,城 4 的度数变成 1。度数谁高谁低先别急着下结论,扫到一半的中间态容易看走眼,等 6 条路全数完再一起比,才知道谁是最忙的枢纽。
度数数完 · deg = [2, 3, 4, 2, 1]：6 条路全数完了。按城市编号排,度数是 [2, 3, 4, 2, 1]:城 2 连了 4 条路最多,城 1 连 3 条,城 0 和城 3 各连 2 条,城 4 只连 1 条最少。度数一出来,谁该拿大值就清楚了:城 2 该拿最大的 5,城 4 拿最小的 1。下面把这些度数排个序,让分配一目了然。
度数按城市编号排成一排：把刚才每座城市的度数抄成一排,从左到右是城 0 到城 4,值分别是 2、3、4、2、1。现在它是乱的,不方便配值。下一步把它从小到大排好,这样越靠右度数越大,正好对应越大的值。
升序排好 · [1, 2, 2, 3, 4]：排好序,现在是 [1, 2, 2, 3, 4]。最左边是最小的度数 1,最右边是最大的度数 4。接下来从左往右走,第 1 个位置配值 1,第 2 个配值 2,一直到第 5 个配值 5。位置越靠右度数越大,拿到的值也越大,这就把大值稳稳配给了大度数。
第 1 位 · 度数 1 配值 1：走到第 1 个位置,这里度数是 1,按规矩配上值 1。这座城市的贡献就是值乘度数,1 × 1 = 1。把它加进累计和,累计从 0 变成 1。继续往右,度数更大的位置会配更大的值。
第 2 位 · 度数 2 配值 2：走到第 2 个位置,这里度数是 2,按规矩配上值 2。这座城市的贡献就是值乘度数,2 × 2 = 4。把它加进累计和,累计从 1 变成 5。继续往右,度数更大的位置会配更大的值。
第 3 位 · 度数 2 配值 3：走到第 3 个位置,这里度数是 2,按规矩配上值 3。这座城市的贡献就是值乘度数,3 × 2 = 6。把它加进累计和,累计从 5 变成 11。继续往右,度数更大的位置会配更大的值。
第 4 位 · 度数 3 配值 4：走到第 4 个位置,这里度数是 3,按规矩配上值 4。这座城市的贡献就是值乘度数,4 × 3 = 12。把它加进累计和,累计从 11 变成 23。继续往右,度数更大的位置会配更大的值。
第 5 位 · 度数 4 配值 5：走到第 5 个位置,这里度数是 4,按规矩配上值 5。这座城市的贡献就是值乘度数,5 × 4 = 20。把它加进累计和,累计从 23 变成 43。这是最大的度数配上了最大的值,贡献也最大。
全部配完 · 答案 = 43：五个位置全配完了。把每位的贡献 1 + 4 + 6 + 12 + 20 加起来,正好是 43。这就是最优分配下所有道路重要性之和的最大值。回头看,大值都落在了度数大的城市上,一分值也没浪费在冷清的城市上,这就是排序不等式给的最优安排。
边界想清:两城一路记 3、示例二核到 20、三城全连时度数相同配值 1 到 3 得 12。
面试重点:贡献拆成值×度数、排序不等式保证大值配大度数最优、O(m + n log n) 且注意长整型防溢出。
参考代码
from __future__ import annotationsfrom 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))复杂度
- 时间：O(m + n log n)，m 是路的条数,数度数扫一遍 roads 是 O(m);再对 n 个度数排序是 O(n log n);最后遍历累加是 O(n)。主导项是排序的 O(n log n),整体就是 O(m + n log n)
- 空间：O(n)，按峰值算,主要是那个长度为 n 的度数数组,O(n)。排序本身的额外开销:C plus plus 和 Java 通常是 O(log n) 递归栈,Python 的排序最坏 O(n),都不超过度数数组的量级,所以整体空间 O(n)
易错点
面试追问把动画讲成自己的话
追问这题的核心洞察是什么?
追问为什么大值配大度数就是最优,能证明吗?
追问复杂度是多少,有什么实现坑?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
网格中的最小路径代价
LeetCode 2304 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题