Computer >> Máy Tính >  >> Lập trình >> C ++

Thời gian tối thiểu để thu thập tất cả táo trong một cây trong C ++

Giả sử chúng ta có một cây vô hướng bao gồm n đỉnh và chúng được đánh số từ 0 đến n-1, trong đó có một số quả táo trên đỉnh của chúng. Chúng tôi dành 1 giây để đi bộ qua một cạnh của cái cây. Chúng ta phải tìm ra thời gian tối thiểu tính bằng giây mà chúng ta phải bỏ ra để thu thập tất cả các quả táo trên cây bắt đầu từ đỉnh 0 và quay trở lại đỉnh này.

Ở đây các cạnh của cây vô hướng được đưa ra trong các cạnh của mảng, trong đó các cạnh [i] =[from_i, to_i] điều này có nghĩa là tồn tại một cạnh nối các đỉnh from_i và to_i. Ngoài ra, có một mảng khác có quả táo, trong đó hasApple [i] =true có nghĩa là đỉnh tôi có quả táo, ngược lại, nó không có quả táo nào.

Vì vậy, nếu đầu vào là n =7 và các cạnh =[[0,1], [0,2], [1,4], [1,5], [2,3], [2,6]] và có apple =[false, false, true, false, true, true, false], thì đầu ra sẽ là 8,

Thời gian tối thiểu để thu thập tất cả táo trong một cây trong C ++

như từ hình trên, chúng ta có thể thấy cái cây mà các đỉnh màu đỏ có một quả táo. Một con đường tối ưu để thu thập tất cả các quả táo được hiển thị bằng các mũi tên màu xanh lục.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Xác định một tập hợp đã truy cập

  • Xác định một hàm dfs (), điều này sẽ lấy nút, mệnh, một mảng a, một đồ thị mảng [],

  • tạm thời:=0

  • cho mỗi phần tử x trong biểu đồ [nút] -

    • nếu x giống mệnh, thì -

      • Bỏ qua phần sau, chuyển sang phần tiếp theo

    • temp:=temp + dfs (x, node, a, graph)

  • ret:=ret + temp * 2

  • trả về true khi [node] + temp> 0, nếu không thì 0

  • Từ phương thức chính, thực hiện như sau -

  • ret:=0

  • Xác định một mảng gồm n danh sách được gọi là đồ thị

  • để khởi tạo i:=0, khi i

    • chèn e [i, 1] vào cuối biểu đồ [e [i, 0]]

    • chèn e [i, 0] vào cuối biểu đồ [e [i, 1]]

  • dfs (0, -1, a, đồ thị)

  • trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

#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));
}

Đầu vào 

7, {{0,1},{0,2},{1,4},{1,5},{2,3},{2,6}},
{false,false,true,false,true,true,false}

Đầu ra 

8