Chương trình tìm ra giá trị nhỏ nhất từ ​​tổng giá trị nút của cây con trong Python

Giả sử, chúng ta có một cây có tất cả các nút của nó được đánh số từ 1 đến n. Mỗi nút chứa một giá trị số nguyên. Bây giờ nếu chúng ta loại bỏ một cạnh khỏi cây, sự khác biệt về tổng giá trị nút của hai cây con phải là nhỏ nhất. Chúng ta phải tìm ra và trả về sự khác biệt tối thiểu giữa các cây con như vậy. Cây được cung cấp cho chúng tôi dưới dạng tập hợp các cạnh và giá trị của các nút cũng được cung cấp.

Vì vậy, nếu đầu vào là n =6, edge_list =[[1, 2], [1, 3], [2, 4], [3, 5], [3, 6]], giá trị =[15, 25, 15, 55, 15, 65], thì đầu ra sẽ là 0.

Nếu cạnh (1,2) bị loại bỏ, tổng các trọng số trở thành 80, 110. Hiệu số là 30.

Nếu cạnh (1,3) bị loại bỏ, tổng các trọng số trở thành 95, 95. Hiệu số là 0.

Nếu cạnh (2,4) bị loại bỏ, tổng các trọng số trở thành 55, 135. Chênh lệch là 80.

Nếu cạnh (3,5) bị loại bỏ, tổng các trọng số trở thành 15, 175. Chênh lệch là 160.

Nếu cạnh (3,6) bị loại bỏ, tổng các trọng số trở thành 65, 125. Chênh lệch là 60.

Vậy trọng lượng tối thiểu là 0.

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

• adj_list:=một danh sách mới có kích thước n chứa các danh sách trống
• đối với mỗi cạnh trong edge_list, hãy thực hiện
  • u:=edge [0]
  • v:=edge [1]
  • chèn v-1 vào cuối adj_list [u-1]
  • chèn u-1 vào cuối adj_list [v-1]
• value_list:=một danh sách mới có kích thước n được khởi tạo bằng các chữ số 0
• not_visited:=một bản đồ mới có kích thước i, trong đó tôi là số lượng danh sách không trống trong adj_list
• trong khi not_visited không trống, hãy thực hiện
  • đối với mỗi tôi trong not_visited, hãy thực hiện
    • value_list [i]:=value_list [i] + các giá trị [i]
    • nếu độ dài của (adj_list [i]) khác 0, thì
      • xóa tôi khỏi adj_list [adj_list [i, 0]]
      • value_list [adj_list [i, 0]]:=value_list [adj_list [i, 0]] + value_list [i]
  • đối với mỗi tôi trong not_visited, hãy thực hiện
    • if len (adj_list [i]) và len (adj_list [adj_list [i, 0]]) ==1, thì
      • not_visited:=một danh sách mới chứa adj_list [i, 0]
• return_val:=| sum (các giá trị) - 2 * value_list [0] |
• đối với tôi trong phạm vi từ 1 đến n, thực hiện
  • quyết định_val:=| sum (các giá trị) - 2 * value_list [i] |
  • nếu quyết định_val
  • return_val:=quyết định_val

Ví dụ

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

def solve(n, edge_list, values):
   adj_list = [[] for i in range(n)]

   for edge in edge_list:
      u = edge[0]
      v = edge[1]
      adj_list[u-1].append(v-1)
      adj_list[v-1].append(u-1)

   value_list = [0] * n
   not_visited = {i for i in range(n) if len(adj_list[i]) == 1}
   while(len(not_visited)):
      for i in not_visited:
         value_list[i] += values[i]
         if(len(adj_list[i])):
            adj_list[adj_list[i][0]].remove(i)
            value_list[adj_list[i][0]] += value_list[i]
      not_visited = {adj_list[i][0] for i in not_visited if
         len(adj_list[i]) and len(adj_list[adj_list[i][0]]) == 1}
   return_val = abs(sum(values) - 2 * value_list[0])

   for i in range(1, n):
      decision_val = abs(sum(values) - 2 * value_list[i])
      if decision_val < return_val:
         return_val = decision_val
   return return_val

print(solve(6, [[1, 2], [1, 3], [2, 4], [3, 5], [3, 6]], [10, 20, 10, 50, 10, 60]))

Đầu vào

6, [[1, 2], [1, 3], [2, 4], [3, 5], [3, 6]], [10, 20, 10, 50, 10, 60]

Đầu ra

0