Имеется древовидная (т. е. связный неориентированный граф без циклов) структурная сеть страны, состоящая из 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; } };