Имеется древовидная (т. е. связный неориентированный граф без циклов) структурная сеть страны, состоящая из n городов с номерами от 0 до n - 1 и ровно n - 1 дорог. Столица — город 0. Вам задан двумерный массив целых чисел roads, где roads[i] = [ai, bi] означает, что существует дорога с двусторонним движением, соединяющая города ai и bi.

Встреча представителей каждого города. Встреча проходит в столице.

В каждом городе есть машина. Вам задано целое число seats, обозначающее количество мест в каждом вагоне.

Представитель может использовать автомобиль в своем городе для поездок или поменять автомобиль и ехать с другим представителем. Стоимость проезда между двумя городами составляет один литр топлива.

Возвратите минимальное количество литров топлива, чтобы добраться до столицы.

Пример 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.

Пример 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.

Пример 3:

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

Ограничения:

  • 1 <= n <= 105
  • roads.length == n - 1
  • roads[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • roads представляет допустимое дерево.
  • 1 <= seats <= 105

Решение:-

Интуиция:

  • Здесь мы должны найти минимальную стоимость топлива для перевозки людей из города (представленного узлом 0) во все другие города (представленные другими узлами) в дорожной сети.

Подход :

  • Итак, мы используем алгоритм поиска в глубину (DFS) для обхода графа, представляющего дорожную сеть.
  • Граф представлен в виде массива связанных списков, где каждый элемент массива представляет узел в графе, а связанный список содержит соседние узлы этого узла.
  • В функции DFS количество людей в каждом городе рассчитывается и сохраняется в переменной people. Это делается, начиная с текущего узла (u) и посещая всех его соседей (v), и добавляя количество людей в каждом соседе к людям.
  • Затем количество автомобилей, необходимых для перевозки людей, рассчитывается путем деления количества людей на количество мест в каждом автомобиле с округлением до ближайшего целого числа.
  • Стоимость — это количество необходимых автомобилей, и она добавляется к переменной ans, которая представляет собой общую стоимость. Значение ans возвращается как результат функции.
  • Функция MinimumFuelCost принимает два параметра: дороги, представляющие собой массив дорог, представленных парами узлов, и сиденья, представляющие собой количество мест в каждом автомобиле.
  • Функция настраивает графическое представление дорожной сети, вызывает функцию DFS для расчета стоимости и возвращает результат.

Пояснение к подходу:

  • Наша цель — вычислить минимальное количество топлива, необходимое для перевозки людей из одного города (города 0) во все другие города дорожной сети.
  • Итак, мы используем алгоритм поиска в глубину для обхода графа дорожной сети и подсчета количества людей в каждом городе.
  • Количество автомобилей, необходимых для перевозки людей из одного города в другой, рассчитывается путем деления количества людей на количество мест в каждом автомобиле с округлением до ближайшего целого числа.
  • Общая стоимость топлива рассчитывается как сумма количества автомобилей, необходимых для перевозки людей между всеми городами.

Сложность

  • Временная сложность: O(n)
  • Пространственная сложность: O(n)

C++

class Solution {
 public:
  long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
    long long ans = 0;
    vector<vector<int>> graph(roads.size() + 1);

    for (const vector<int>& road : roads) {
      const int u = road[0];
      const int v = road[1];
      graph[u].push_back(v);
      graph[v].push_back(u);
    }

    dfs(graph, 0, -1, seats, ans);
    return ans;
  }

 private:
  int dfs(const vector<vector<int>>& graph, int u, int prev, int seats,
          long long& ans) {
    int people = 1;
    for (const int v : graph[u]) {
      if (v == prev)
        continue;
      people += dfs(graph, v, u, seats, ans);
    }
    if (u > 0)
      // # of cars needed = ceil(people / seats)
      ans += (people + seats - 1) / seats;
    return people;
  }
};