Chương trình tìm 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 với các nút được đánh số từ 1 đến n. Mỗi nút chứa một giá trị nguyên. Nếu loại bỏ một cạnh từ cây, hiệu số giữa tổng giá trị nút của hai cây con phải tối thiểu. Chúng ta phải tìm và trả về hiệu số nhỏ nhất giữa các cây con như vậy. Cây được cho dưới dạng tập hợp các cạnh, và giá trị các nút cũng được cung cấp.

Ví dụ: n = 6, edge_list = [[1, 2], [1, 3], [2, 4], [3, 5], [3, 6]], values = [15, 25, 15, 55, 15, 65], thì kết quả sẽ là 0.

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

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

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

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

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

Vậy hiệu số nhỏ nhất là 0.

Để giải quyết bài toán này, ta thực hiện các bước sau:

• adj_list := danh sách mới kích thước n chứa các danh sách rỗng
• Với mỗi cạnh trong edge_list:
  • u := edge[0]
  • v := edge[1]
  • Thêm v-1 vào cuối adj_list[u-1]
  • Thêm u-1 vào cuối adj_list[v-1]
• value_list := danh sách mới kích thước n khởi tạo bằng 0
• not_visited := tập hợp mới kích thước i, với i là số danh sách không rỗng trong adj_list
• Khi not_visited không rỗng:
  • Với mỗi i trong not_visited:
    • value_list[i] := value_list[i] + values[i]
    • Nếu độ dài adj_list[i] khác 0:
      • Xóa i khỏi adj_list[adj_list[i][0]]
      • value_list[adj_list[i][0]] := value_list[adj_list[i][0]] + value_list[i]
  • Cập nhật not_visited: tập các adj_list[i][0] với i trong not_visited nếu độ dài adj_list[i] và adj_list[adj_list[i][0]] đều bằng 1
• return_val := |sum(values) - 2 * value_list[0]|
• Với i từ 1 đến n-1:
  • decision_val := |sum(values) - 2 * value_list[i]|
  • Nếu decision_val < return_val: return_val := decision_val
• Trả về return_val

Ví dụ triển khai

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