每日一题 2477. 到达首都的最少油耗（中等，树）

去参加CCF软件大会，好多天没做每日一题了
我的思路：

1. 看到题目是一个由叶子节点向根节点汇聚的过程，就想到拓扑排序
2. 每次移动都只将叶子节点向前移动一格，并删除它，此时移动的目标节点数量加一，并根据该叶子节点此时的数量增加油耗，同时将新的叶子节点加入队列中，知道队列中只剩下根节点
3. 但是上面的做法没有考虑到官方题解的思路，当dfs时，每次递归就包含了所有子节点的信息，直接统计数量计算油耗即可
4. 下面是我的代码和官方题解

class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        edges = defaultdict(list)
        deg = [0] * (len(roads) + 1)
        for r in roads:
            edges[r[0]].append(r[1])
            edges[r[1]].append(r[0])
            deg[r[0]] += 1
            deg[r[1]] += 1
        
        fa = {}
        leaf = []
        def dfs(node, last):
            if len(edges[node]) == 1 and node != 0:
                leaf.append(node)
            for i in edges[node]:
                if i == last:
                    continue
                fa[i] = node
                dfs(i, node)

        dfs(0, -1)
        ans = 0
        nums = [1] * (len(roads) + 1)
        while len(leaf) > 0:
            
            t = []
            for i in range(len(leaf)):
                if leaf[i] == 0:
                    continue
                deg[fa[leaf[i]]] -= 1
                if deg[fa[leaf[i]]] == 1:
                    t.append(fa[leaf[i]])
                ans += ceil(nums[leaf[i]] / seats)
                nums[fa[leaf[i]]] += nums[leaf[i]]

            leaf = t

        return ans

class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        g = [[] for i in range(len(roads) + 1)]
        for e in roads:
            g[e[0]].append(e[1])
            g[e[1]].append(e[0])
        res = 0
        def dfs(cur, fa):
            nonlocal res
            peopleSum = 1 
            for ne in g[cur]:
                if ne != fa:
                    peopleCnt = dfs(ne, cur)
                    peopleSum += peopleCnt
                    res += (peopleCnt + seats - 1) // seats
            return peopleSum
        dfs(0, -1)
        return res

作者：力扣官方题解
链接：https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital/solutions/2553190/dao-da-shou-du-de-zui-shao-you-hao-by-le-v013/
来源：力扣（LeetCode）

代码007普通

打赏 收藏 海报 链接