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

本文主要是介绍【算法思考记录】力扣2477. 到达首都的最少油耗【C++，深度优先搜索】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接

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

题目解析

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

输入说明

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

输出说明

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

题解思路

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

C++ 代码实现

class Solution {
public:long long minimumFuelCost(vector<vector<int>>& roads, int seats) {unordered_map<int, vector<int>> graph;for (auto &v : roads) {int x = v[0], y = v[1];graph[x].push_back(y);graph[y].push_back(x);}long long ans = 0;function<long long(long long, long long)> dfs = [&] (long long node, long long fa) {long long size = 1;for (auto &chi : graph[node]) {if (chi == fa) continue;size += dfs(chi, node);}if (node) {// 向上取整的技巧性写法。ans += (size - 1) / seats + 1;}return size;};dfs(0, 0);return ans;}
};