洛阳哪里有做网站的,织梦小说网站模板下载,汉中门户网官网,网络网站租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 表示每辆车里面座位的数目。
城市里的代表可以选择乘坐所在城市的车或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。
请你返回到达首都最少需要多少升汽油。 题目可以抽象为一个以0为根节点的树。
题目汽油数可以转换为每一条边的需要的车辆数因为最大容量固定进而转化为每一条求每一条边经过了多少个人进而转化为求每条边连接的邻接点的子树的节点个数。 每条边需要的车 每条边经过的人数/ 最大容量 上取整。 n/m上取整 ( n m -1 ) / n 每条边经过的人 该边 邻接点子树节点的个数。 可用使用dfs来解决 dfs(i):以i为根节点子树的个数(包括根节点)。 int dfs(i): res0 for j in i 的邻接点列表 resdfs(j) return res1 建图可以使用vector建立无向图。
C vector建立无向图并遍历-CSDN博客 class Solution {
private:long long res 0;vectorvectorintg;int seat;int dfs(int i,int pre){int cnt0;for(auto ne:g[i]){if(nei||nepre) continue;int t dfs(ne,i);cntt;res(tseat-1)/seat;}return cnt1;}
public:long long minimumFuelCost(vectorvectorint roads, int seats) {int n roads.size();g.resize(n1);seatseats;for(auto e:roads){g[e[0]].push_back(e[1]);g[e[1]].push_back(e[0]);}dfs(0,-1);return res;}
};
在使用dfs遍历邻接点的时候如果相对每个子树都进行相同的操作在for循环里面写。
