[LeetCode] 2477. Minimum Fuel Cost to Report to the Capital

There is a tree (i.e., a connected, undirected graph with no cycles) structure country network consisting of n cities numbered from 0 to n - 1 and exactly n - 1 roads. The capital city is city 0. You are given a 2D integer array roads where roads[i] = [ai, bi] denotes that there exists a bidirectional road connecting cities ai and bi.

There is a meeting for the representatives of each city. The meeting is in the capital city.

There is a car in each city. You are given an integer seats that indicates the number of seats in each car.

A representative can use the car in their city to travel or change the car and ride with another representative. The cost of traveling between two cities is one liter of fuel.

Return the minimum number of liters of fuel to reach the capital city.

Example 1:

Input: roads = [[0,1],[0,2],[0,3]], seats = 5
Output: 3
Explanation: 
- Representative1 goes directly to the capital with 1 liter of fuel.
- Representative2 goes directly to the capital with 1 liter of fuel.
- Representative3 goes directly to the capital with 1 liter of fuel.
It costs 3 liters of fuel at minimum. 
It can be proven that 3 is the minimum number of liters of fuel needed.

Example 2:

Input: roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2
Output: 7
Explanation: 
- Representative2 goes directly to city 3 with 1 liter of fuel.
- Representative2 and representative3 go together to city 1 with 1 liter of fuel.
- Representative2 and representative3 go together to the capital with 1 liter of fuel.
- Representative1 goes directly to the capital with 1 liter of fuel.
- Representative5 goes directly to the capital with 1 liter of fuel.
- Representative6 goes directly to city 4 with 1 liter of fuel.
- Representative4 and representative6 go together to the capital with 1 liter of fuel.
It costs 7 liters of fuel at minimum. 
It can be proven that 7 is the minimum number of liters of fuel needed.

Example 3:

Input: roads = [], seats = 1
Output: 0
Explanation: No representatives need to travel to the capital city.

Constraints:

• 1 <= n <= 105
• roads.length == n - 1
• roads[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• roads represents a valid tree.
• 1 <= seats <= 105

到达首都的最少油耗。

给你一棵 n 个节点的树（一个无向、连通、无环图），每个节点表示一个城市，编号从 0 到 n - 1 ，且恰好有 n - 1 条路。0 是首都。给你一个二维整数数组 roads ，其中 roads[i] = [ai, bi] ，表示城市 ai 和 bi 之间有一条 双向路 。

每个城市里有一个代表，他们都要去首都参加一个会议。

每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目。

城市里的代表可以选择乘坐所在城市的车，或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。

请你返回到达首都最少需要多少升汽油。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这是一道图论的题，思路是后序遍历。注意题目给的是连通的无向无环图，所以我们首先要做的还是把图建立起来。图建好之后，因为最终的目的地是 0，那么我们还是需要通过后序遍历先走到图的最末端，然后往节点 0 返回每个 node 需要的座位数。注意最后需要返回的数据类型是 long，所以 res 的计算方法有一点技巧。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     long res = 0;
 3     int seats;
 4 
 5     public long minimumFuelCost(int[][] roads, int seats) {
 6         this.seats = seats;
 7         List<List<Integer>> g = new ArrayList<>();
 8         for (int i = 0; i < roads.length + 1; i++) {
 9             g.add(new ArrayList<>());
10         }
11         for (int[] r : roads) {
12             g.get(r[0]).add(r[1]);
13             g.get(r[1]).add(r[0]);
14         }
15         dfs(g, 0, 0);
16         return res;
17     }
18 
19     private int dfs(List<List<Integer>> g, int cur, int prev) {
20         int people = 1;
21         for (int nei : g.get(cur)) {
22             if (nei == prev) {
23                 continue;
24             }
25             people += dfs(g, nei, cur);
26         }
27         if (cur != 0) {
28             res += (people + seats - 1) / seats;
29         }
30         return people;
31     }
32 }

LeetCode 题目总结