資料結構
網路
關係資料庫管理系統 (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 次瀏覽
