目录

2477. 到达首都的最少油耗

题目描述：

实现代码与解析：

dfs

---

2477. 到达首都的最少油耗

题目描述：

        给你一棵 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 <= 105
• roads.length == n - 1
• roads[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• roads 表示一棵合法的树。
• 1 <= seats <= 105

实现代码与解析：

dfs

C++

class Solution {
public:vector<int> e = vector<int>(200010, 0), ne = vector<int>(200010, 0), h = vector<int>(100010, -1);vector<bool> q = vector<bool>(100010, false);int idx = 0;long long res = 0;void add (int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;}int dfs (int cur, int seats) {int sum = 1;q[cur] = true; // 标记,避免反向遍历回去for (int i = h[cur]; ~i; i = ne[i]) {int j = e[i];if (!q[j])  sum += dfs(j, seats);     }if (cur != 0) res += (sum + seats - 1) / seats; return sum;}long long minimumFuelCost(vector<vector<int>>& roads, int seats) {for (int i = 0; i < roads.size(); i++) {int a = roads[i][0];int b = roads[i][1];add(a, b);add(b, a);}dfs(0, seats);return res;}
};

Java

class Solution {public int idx = 0;public int N = 100010;public int[] h = new int[N], e = new int[N*2], ne = new int[N*2];public boolean[] q = new boolean[N];public long res = 0;public void add(int a, int b)  {e[idx] = b; ne[idx] = h[a]; h[a] = idx++;}public int dfs(int cur, int seats) {int sum = 1;q[cur] = true;for (int i = h[cur]; i != -1; i = ne[i]) {int j = e[i];if (!q[j]) sum += dfs(j, seats);}if (cur != 0) res += (sum + seats - 1) / seats;return sum;}public long minimumFuelCost(int[][] roads, int seats) {Arrays.fill(h, -1);for (int i = 0; i < roads.length; i++) {int a = roads[i][0];int b = roads[i][1];add(a, b);add(b, a);}dfs(0, seats);return res;}
}

原理思路：

        深度优先遍历，从首都开始遍历，从叶子节点向首都返回人数，后序每经过一个节点，就加上此节点的人，同时计算一下需要的车辆，也就是下一路程需要的油，最后到首都后就不在计算，因为已经到终点了。

        res += (sum + seats - 1) / seats;  是用来向上取整的。

还有记得记录以及走过的节点，避免往回走，无限递归。