php网站建设教程 电子书,微信浏览为网站的缓存怎么清理,品牌网络推广方案,安阳建筑设计【LetMeFly】2477.到达首都的最少油耗#xff1a;深度优先搜索(DFS)
力扣题目链接#xff1a;https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital/
给你一棵 n 个节点的树#xff08;一个无向、连通、无环图#xff09;#xff0c;每个节点表示一…【LetMeFly】2477.到达首都的最少油耗深度优先搜索(DFS)
力扣题目链接https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital/
给你一棵 n 个节点的树一个无向、连通、无环图每个节点表示一个城市编号从 0 到 n - 1 且恰好有 n - 1 条路。0 是首都。给你一个二维整数数组 roads 其中 roads[i] [ai, bi] 表示城市 ai 和 bi 之间有一条 双向路 。
每个城市里有一个代表他们都要去首都参加一个会议。
每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目。
城市里的代表可以选择乘坐所在城市的车或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。
请你返回到达首都最少需要多少升汽油。 示例 1 输入roads [[0,1],[0,2],[0,3]], seats 5
输出3
解释
- 代表 1 直接到达首都消耗 1 升汽油。
- 代表 2 直接到达首都消耗 1 升汽油。
- 代表 3 直接到达首都消耗 1 升汽油。
最少消耗 3 升汽油。示例 2 输入roads [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats 2
输出7
解释
- 代表 2 到达城市 3 消耗 1 升汽油。
- 代表 2 和代表 3 一起到达城市 1 消耗 1 升汽油。
- 代表 2 和代表 3 一起到达首都消耗 1 升汽油。
- 代表 1 直接到达首都消耗 1 升汽油。
- 代表 5 直接到达首都消耗 1 升汽油。
- 代表 6 到达城市 4 消耗 1 升汽油。
- 代表 4 和代表 6 一起到达首都消耗 1 升汽油。
最少消耗 7 升汽油。示例 3 输入roads [], seats 1
输出0
解释没有代表需要从别的城市到达首都。提示
1 n 105roads.length n - 1roads[i].length 20 ai, bi nai ! biroads 表示一棵合法的树。1 seats 105
方法一深度优先搜索(DFS)
车是可以随时“丢弃”与“重选”的因此我们只需要知道“每一步”有多少人即可。
从“根节点”0开始深搜深搜过程中对于节点node 假设node有数个子节点各个子节点为根的子树的大小分别为 a 1 a_1 a1 a 2 a_2 a2… 那么从这些节点到达节点node分别需要耗油 ⌈ a 1 s e a t s ⌉ \lceil\frac{a_1}{seats}\rceil ⌈seatsa1⌉ ⌈ a 2 s e a t s ⌉ \lceil\frac{a_2}{seats}\rceil ⌈seatsa2⌉… 将这些耗油累加到答案中同时也得到了以节点node为根的子树的大小。 上述过程中所有人一同往根节点的方向走一步就将耗油累加到了答案中因此最终返回答案即可。
时间复杂度 O ( N 2 ) O(N^2) O(N2)空间复杂度 O ( N log N ) O(N\log N) O(NlogN)
AC代码
C
class Solution {
private:long long ans;vectorvectorint graph;vectorbool visited;long long dfs(int node, int seats){visited[node] true;int cnt 1;for (int toNode : graph[node]) {if (!visited[toNode]) {long long peopleFromThatNode dfs(toNode, seats);cnt peopleFromThatNode;ans (peopleFromThatNode seats - 1) / seats;}}return cnt;}public:long long minimumFuelCost(vectorvectorint roads, int seats) {ans 0;graph vectorvectorint(roads.size() 1);visited vectorbool(roads.size() 1);for (auto road : roads) {graph[road[0]].push_back(road[1]);graph[road[1]].push_back(road[0]);}dfs(0, seats);return ans;}
};Python
# from typing import Listclass Solution:def dfs(self, node: int) - int:self.visited[node] Truecnt 1for nextNode in self.graph[node]:if not self.visited[nextNode]:peopleFromThatNode self.dfs(nextNode)cnt peopleFromThatNodeself.ans (peopleFromThatNode self.seats - 1) // self.seatsreturn cntdef minimumFuelCost(self, roads: List[List[int]], seats: int) - int:self.ans 0self.graph [[] for _ in range(len(roads) 1)]for from_, to in roads:self.graph[from_].append(to)self.graph[to].append(from_)self.visited [False] * (len(roads) 1)self.seats seatsself.dfs(0)return self.ans同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/134816086
