数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++中收集树中所有苹果的最小时间
假设我们有一棵包含n个顶点的无向树，这些顶点编号从0到n-1，其中一些顶点上有苹果。我们走过树的一条边需要花费1秒。我们必须找到从顶点0出发收集所有苹果并返回到该顶点所需花费的最小时间（单位：秒）。
此处，无向树的边在数组edges中给出，其中edges[i] = [from_i, to_i]表示存在连接顶点from_i和to_i的边。此外，还有一个数组hasApple，其中hasApple[i] = true表示顶点i上有苹果，否则表示没有苹果。
因此，如果输入类似于n = 7，edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]]，以及hasApple = [false, false, true, false, true, true, false]，则输出为8。
从上图可以看出，红色顶点上有苹果。绿色箭头显示了一条收集所有苹果的最佳路径。
为了解决这个问题，我们将遵循以下步骤：
定义一个集合visited
定义一个函数dfs()，它将接收节点、父节点、数组a和数组graph[]。
temp := 0
对于graph[node]中的每个元素x：
如果x与父节点par相同，则：
忽略以下部分，跳过到下一迭代。
temp := temp + dfs(x, node, a, graph)
ret := ret + temp * 2
当a[node] + temp > 0时返回true，否则返回0。
在主方法中执行以下操作：
ret := 0
定义一个包含n个列表的数组graph
初始化i := 0，当i < e的大小，更新（i增加1），执行：
将e[i, 1]插入到graph[e[i, 0]]的末尾。
将e[i, 0]插入到graph[e[i, 1]]的末尾。
dfs(0, -1, a, graph)
返回ret
示例
让我们看看下面的实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
class Solution {
public:
set<int> visited;
int ret;
int dfs(int node, int par, vector<bool>& a, vector<int> graph[]){
int temp = 0;
for (int x : graph[node]) {
if (x == par)
continue;
temp += dfs(x, node, a, graph);
}
ret += temp * 2;
return a[node] + temp > 0;
}
int minTime(int n, vector<vector<int> >& e, vector<bool>& a){
ret = 0;
vector<int> graph[n];
for (int i = 0; i < e.size(); i++) {
graph[e[i][0]].push_back(e[i][1]);
graph[e[i][1]].push_back(e[i][0]);
}
dfs(0, -1, a, graph);
return ret;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,1},{0,2},{1,4},{1,5},{2,3},{2,6}};
vector<bool> v1 = {false,false,true,false,true,true,false};
cout << (ob.minTime(7,v, v1));
}输入
7, {{0,1},{0,2},{1,4},{1,5},{2,3},{2,6}},
{false,false,true,false,true,true,false}输出
8
416 次浏览
