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

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

原题链接

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

题目解析

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

输入说明

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

输出说明

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

题解思路

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

Java 代码实现

class Solution {private long ans;private int dfs(int node, int fa, List<Integer>[] graph, int seats) {int size = 1;for (int chi : graph[node]) {if (chi == fa) {continue;}size += dfs(chi, node, graph, seats);}if (node != 0) {ans += (size - 1) / seats + 1;}return size;}public long minimumFuelCost(int[][] roads, int seats) {int n = roads.length + 1;List<Integer>[] graph = new ArrayList[n];Arrays.setAll(graph, e -> new ArrayList<>());for (int[] e : roads) {int x = e[0], y = e[1];graph[x].add(y);graph[y].add(x);}dfs(0, 0, graph, seats);return ans;}
}