.net商城网站模板下载,网站开发怎么对接客户,网站建设新发展,漯河市建设工程信息网2477. 到达首都的最少油耗
给你一棵 n 个节点的树#xff08;一个无向、连通、无环图#xff09;#xff0c;每个节点表示一个城市#xff0c;编号从 0 到 n - 1 #xff0c;且恰好有 n - 1 条路。0 是首都。给你一个二维整数数组 roads #xff0c;其中 roads[i] [ai,…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
class Solution {
public:long long minimumFuelCost(vectorvectorint roads, int seats) {vectorvectorint adjacencyList(roads.size() 1);// 构建邻接表for (auto edge : roads) {int city1 edge[0], city2 edge[1];adjacencyList[city1].push_back(city2);adjacencyList[city2].push_back(city1);}long long totalFuel 0;functionint(int, int) dfs [](int currentCity, int parentCity) - int {int subtreeSize 1;
//lambda表达式// 遍历邻居节点for (int neighbor : adjacencyList[currentCity]) {if (neighbor ! parentCity) {subtreeSize dfs(neighbor, currentCity);}}// 如果当前城市不是根节点计算需要的油耗if (currentCity ! 0) {totalFuel (subtreeSize - 1) / seats 1; }return subtreeSize;};dfs(0, -1); // 从根节点开始深度优先搜索return totalFuel;}
};参考了灵神的题解
