原题链接:
https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital/description/

解法1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    final int N = (int)(2e5 + 10);
    int [] e = new  int [N];
    int [] h = new  int [N];
    int [] ne = new  int [N];
    int idx = 0;
    int seats;
    // 将b插入到a
    void add(int a,int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++; 
    }

    public long minimumFuelCost(int[][] roads, int seats) {
        this.seats = 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,-1);

        return ans;
    }
    private long ans;

    private int dfs(int x,int fa){
        int size = 1;
        for(int i = h[x] ; i != -1 ;i = ne[i]){
            int j = e[i];
            if(j != fa){
                size += dfs(j,x);
            }
        }

        if(x > 0){
            ans += (size - 1)  / seats + 1;
        }

        return size;
    }
}