本题还是比较有意思的,跟以往图论有所不同的是,之前的图论大部分都是二维或者三维数组(类似迷宫问题那样),本题则是邻接表,也可以是树形存储方式。
题目:
题目链接:大臣的旅费
很久以前,T 王国空前繁荣。为了更好地管理国家,王国修建了大量的快速路,用于连接首都和王国内的各大城市。为节省经费,T 国的大臣们经过思考,制定了一套优秀的修建方案,使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。
同时,如果不重复经过大城市,从首都到达每个大城市的方案都是唯一的。J 是 T 国重要大臣,他巡查于各大城市之间,体察民情。所以,从一个城市马不停蹄地到另一个城市成了 J 最常做的事情。他有一个钱袋,用于存放往来城市间的路费。聪明的 J 发现,如果不在某个城市停下来修整,在连续行进过程中,他所花的路费与他已走过的距离有关。
具体来说,一段连续的旅途里,第 1 千米的花费为 11,第 2 千米的花费为 12,第 3 千米的花费为 13,…,第 x 千米的花费为 x+10。也就是说,如果一段旅途的总长度为 1 千米,则刚好需要花费 11,如果一段旅途的总长度为 2 千米,则第 1 千米花费 11,第 2 千米花费 12,一共需要花费 11+12=23。
J 大臣想知道:他从某一个城市出发,中间不休息,到达另一个城市,所有可能花费的路费中最多是多少呢?
输入格式
输入的第一行包含一个整数 n,表示包括首都在内的 T 王国的城市数。城市从 1 开始依次编号,1 号城市为首都。接下来 n−1 行,描述 T 国的高速路(T 国的高速路一定是 n−1条)。
每行三个整数 Pi,Qi,Di,表示城市 Pi 和城市 Qi 之间有一条双向高速路,长度为 Di 千米。
输出格式
输出一个整数,表示大臣 J 最多花费的路费是多少。
数据范围
1≤n≤105,
1≤Pi,Qi≤n,
1≤Di≤1000
输入样例:
5
1 2 2
1 3 1
2 4 5
2 5 4
输出样例:
135
思路:
本题有个巧妙的思路,求花费最多路费就是求最长路径问题,而花费和路程之间有个关系式为 总花费 = 10 * 总长度 + (1 + 总长度)* 总长度 /2
本题求路径总长度有一种说法是求树的直径问题,因为本题图的结构可以看作是树,树的直径则是树的最大长度问题。
如何求树的直径呢?
很简单,只需要两步
- 首先任选一点 x,求出离该点最远的点 y
- 选取 y 点重复上述操作,选取离 y 点最远的点 z
这样就可以求得树的直径,直径为 y 到 z 点的距离。
这个方法也很好证明,大家使用反证法就可以得出,这里就只说求求解方法不细说证明过程了。因为证明过程不是本题重点。
可能本题第一眼看上去是需要构造树来进行存储,但是图论中的存储基本是用不到树的(就我个人而言,构造树来存储很麻烦,一是不会构造树,二是构造了树也不会存储),这里可以用邻接表来存储。
图的存储
图一般有两种存储方式:
- 邻接矩阵
开个二维数组,g[i][j] 表示点 i 和点 j 之间的边权。邻接矩阵适合处理小规模问题。
- 邻接表
邻接表有两种常用写法,我推荐第二种,代码更简洁,效率也更高。
(1) 二维vector:vector<vector> edge,edge[i][j] 表示第 i 个点的第 j 条邻边。
(2) 数组模拟邻接表:为每个点开个单链表,分别存储该点的所有邻边。
因为本题是无向图,所以往返两个点都要存
python">h = [[] for i in range(n + 1)]
for i in range(n - 1):
p, q, d = map(int, input().split())
h[p].append([q, d])
h[q].append([p, d])
思路有了,表的存储结构也有了,那么如何实现求树的最长直径呢?
这里可以用dfs或者bfs来搜索最短路径,因为可能会回到本身,所以在搜索时要把走过路程不做二次选择。
方法一:DFS
在搜索之前需要创建一个数组用来存储路径。首先任选一点,因为搜索时要判断不能走之前走过的点(也就是前一个点),所以dfs函数多加一个参数来记录前一个走过的结点,dfs函数还需要一个参数来记录走到该点时的距离为多少。
dfs函数 代码如下:
python">def dfs(node, father, distance):
dist[node] = distance
for i, j in h[node]:
if i != father:
dfs(i, node, distance + j)
dist = [0 for _ in range(n + 1)]
dfs(1, -1, 0)
max_index = dist.index(max(dist))
# dist = [0 for _ in range(n + 1)] (可以省略,没有必要写)
dfs(max_index, -1, 0zh)
max_distance = max(dist)
第一个dfs(1, -1, 0)表示任选一个节点1,节点1的上一个节点不存在,所以定义为-1(只要是不存在的节点就行),走到该点时的距离为0(初始距离为0)
max_index 表示离1节点最远的节点,之后重复dfs,找到最远距离max_distance
代码及详细注释:
python">n = int(input())
h = [[] for i in range(n + 1)]
# 构建邻接表,h[i]存储与节点i相连的节点及距离
for i in range(n - 1):
p, q, d = map(int, input().split())
h[p].append([q, d])
h[q].append([p, d])
# 深度优先搜索函数,计算每个节点到根节点的距离
def dfs(node, father, distance):
dist[node] = distance
for i, j in h[node]:
if i != father:
dfs(i, node, distance + j)
dist = [0 for _ in range(n + 1)]
dfs(1, -1, 0)
max_index = dist.index(max(dist)) # 找到距离最远的节点
# dist = [0 for _ in range(n + 1)] (可以省略,没有必要写)
dfs(max_index, -1, 0)
max_distance = max(dist)
# 计算结果并输出
print(10 * max_distance + (1 + max_distance) * max_distance // 2)
方法二:BFS
BFS思路和DFS相同,不过BFS没有爆栈风险,可以放心写。
代码及详细注释:
python">from collections import deque
n = int(input())
h = [[] for i in range(n + 1)]
# 构建邻接表,h[i]存储与节点i相连的节点及距离
for i in range(n - 1):
p, q, d = map(int, input().split())
h[p].append([q, d])
h[q].append([p, d])
# 宽度优先搜索函数,计算从节点u出发的最远距离和对应的节点
def bfs(u):
q = deque()
q.append(u)
dist = [-1 for _ in range(n + 1)]
dist[u] = 0
while q:
node = q.popleft()
for path in h[node]:
val, distance = path[0], path[1]
if dist[val] == -1:
dist[val] = dist[node] + distance
q.append(val)
max_dist = max(dist)
max_index = dist.index(max_dist)
return max_dist, max_index
max_distance, max_index = bfs(1) # 从节点1出发计算最远距离和对应节点
max_distance, max_index = bfs(max_index) # 从最远节点出发再次计算
# 计算结果并输出
print(10 * max_distance + (1 + max_distance) * max_distance // 2)
总结:
本篇博客可以说是上一篇博客的延伸版,上一篇博客全球变暖,讲解bfs和dfs更详细的,本篇博客更多的是邻接表的构建和树的直径问题。