C++でツリー内のすべてのリンゴを収集するための最小時間

n個の頂点で構成される無向ツリーがあり、これらの番号が0からn-1で、頂点にいくつかのリンゴがあるとします。木の片方の端を歩くのに1秒かかります。頂点0から始まり、この頂点に戻るツリー内のすべてのリンゴを収集するために費やす必要のある最小時間を秒単位で見つける必要があります。

ここで、無向ツリーのエッジは配列のエッジで指定されます。ここで、edges [i] =[from_i、to_i]は、頂点from_iとto_iを接続するエッジが存在することを意味します。さらに、別の配列にリンゴがあります。hasApple[i] =trueは、頂点iにリンゴがあることを意味します。それ以外の場合は、リンゴがありません。

したがって、入力がn =7で、edges =[[0,1]、[0,2]、[1,4]、[1,5]、[2,3]、[2,6]]の場合、およびapple =[false、false、true、false、true、true、false]の場合、出力は8になります

上の画像から、赤い頂点にリンゴがある木を見ることができます。すべてのリンゴを収集するための1つの最適なパスは、緑色の矢印で示されています。

これを解決するには、次の手順に従います-

• 訪問した1セットを定義する

• 関数dfs（）を定義します。これは、ノード、パー、配列a、配列グラフ[]、

  を取ります。

• temp：=0

• グラフ[ノード]の各要素xについて-

  • xがparと同じ場合、-

    • 次の部分を無視し、次の反復にスキップします

  • temp：=temp + dfs（x、node、a、graph）

• ret：=ret + temp * 2

• a [node] + temp> 0の場合はtrueを返し、それ以外の場合は0

  を返します。

• メインの方法から、次のようにします-

• ret：=0

• グラフと呼ばれるn個のリストの配列を定義する

• 初期化i：=0の場合、i

  • グラフの最後にe[i、1]を挿入します[e [i、0]]

  • グラフの最後にe[i、0]を挿入します[e [i、1]]

• dfs（0、-1、a、グラフ）

• 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