【算法思考记录】力扣2477. 到达首都的最少油耗【Python3，深度优先搜索】

原题链接

到达首都的最少油耗：一种优雅的解决方案

题目解析

这个算法题目描述了一个有趣的场景：一棵由城市和道路组成的树形结构，其中每个节点代表一个城市，边代表道路。所有城市的代表需要前往编号为0的城市——首都参加会议。任务是计算代表们到达首都所需的最小油耗，假设每座城市只有一辆车，且每辆车的座位数相同。

输入说明

• roads: 一个二维数组，表示城市间的双向道路。
• seats: 整数，表示每辆车的座位数。

输出说明

• 返回一个整数，表示最小的油耗总量。

题解思路

这个问题可以转化为遍历树的问题。对于树中的每一个非首都节点，计算它的子树中有多少个节点，并将这个数除以座位数向上取整，得到的就是从该节点到首都所需的最少油耗。最后，将所有这些油耗相加即可。

Python3 代码实现

from math import ceil

class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        n = len(roads) + 1
        g = {node : [] for node in range(n)}
        for x, y in roads:
            g[x].append(y)
            g[y].append(x)
        ans = 0
        
        def dfs(node, fa):
            size = 1
            for chi in g[node]:
                if chi == fa: continue
                size += dfs(chi, node)

            if node:
                nonlocal ans
                ans += ceil(size / seats)

            return size

        dfs(0, 0)
        return ans

解释

1. 创建一个图 g，存储每个城市的相邻城市。
2. 使用深度优先搜索（DFS）遍历树，计算每个子树的大小。
3. 对于每个子树，将其大小除以座位数并向上取整，得到的结果加到总油耗 ans。
4. 返回总油耗。

结论

这个题解提供了一个高效且清晰的方法来解决“到达首都的最少油耗”问题，展示了如何利用树的结构和深度优先搜索算法来优雅地解决实际问题。