做衣服的教程网站,上海有哪些网络公司,佛山网站建设官网,肯尼亚网站域名目录 2477. 到达首都的最少油耗
题目描述#xff1a;
实现代码与解析#xff1a;
dfs 2477. 到达首都的最少油耗
题目描述#xff1a; 给你一棵 n 个节点的树#xff08;一个无向、连通、无环图#xff09;#xff0c;每个节点表示一个城市#xff0c;编号从 0 到 n…目录 2477. 到达首都的最少油耗
题目描述
实现代码与解析
dfs 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 105roads.length n - 1roads[i].length 20 ai, bi nai ! biroads 表示一棵合法的树。1 seats 105
实现代码与解析
dfs
C
class Solution {
public:vectorint e vectorint(200010, 0), ne vectorint(200010, 0), h vectorint(100010, -1);vectorbool q vectorbool(100010, false);int idx 0;long long res 0;void add (int a, int b) {e[idx] b, ne[idx] h[a], h[a] idx;}int dfs (int cur, int seats) {int sum 1;q[cur] true; // 标记,避免反向遍历回去for (int i h[cur]; ~i; i ne[i]) {int j e[i];if (!q[j]) sum dfs(j, seats); }if (cur ! 0) res (sum seats - 1) / seats; return sum;}long long minimumFuelCost(vectorvectorint roads, int seats) {for (int i 0; i roads.size(); i) {int a roads[i][0];int b roads[i][1];add(a, b);add(b, a);}dfs(0, seats);return res;}
};
Java
class Solution {public int idx 0;public int N 100010;public int[] h new int[N], e new int[N*2], ne new int[N*2];public boolean[] q new boolean[N];public long res 0;public void add(int a, int b) {e[idx] b; ne[idx] h[a]; h[a] idx;}public int dfs(int cur, int seats) {int sum 1;q[cur] true;for (int i h[cur]; i ! -1; i ne[i]) {int j e[i];if (!q[j]) sum dfs(j, seats);}if (cur ! 0) res (sum seats - 1) / seats;return sum;}public long minimumFuelCost(int[][] roads, int 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, seats);return res;}
}
原理思路 深度优先遍历从首都开始遍历从叶子节点向首都返回人数后序每经过一个节点就加上此节点的人同时计算一下需要的车辆也就是下一路程需要的油最后到首都后就不在计算因为已经到终点了。 res (sum seats - 1) / seats; 是用来向上取整的。
还有记得记录以及走过的节点避免往回走无限递归。
