資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python程式：查詢子樹節點值之和的最小值
假設我們有一棵樹，其所有節點編號為1到n。每個節點包含一個整數值。現在，如果我們從樹中移除一條邊，則兩棵子樹的節點值之和的差必須最小。我們必須找出並返回此類子樹之間最小的差值。樹以邊的集合形式提供給我們，節點的值也已提供。
因此，如果輸入類似於n = 6，edge_list = [[1, 2], [1, 3], [2, 4], [3, 5], [3, 6]]，values = [15, 25, 15, 55, 15, 65]，則輸出將為0。
如果移除邊(1,2)，則權重之和變為80, 110。差值為30。
如果移除邊(1,3)，則權重之和變為95, 95。差值為0。
如果移除邊(2,4)，則權重之和變為55, 135。差值為80。
如果移除邊(3,5)，則權重之和變為15, 175。差值為160。
如果移除邊(3,6)，則權重之和變為65, 125。差值為60。
所以最小權重為0。
為了解決這個問題，我們將遵循以下步驟：
- adj_list := 一個大小為n的新列表，包含空列表
- 對於edge_list中的每條邊，執行：
- u := edge[0]
- v := edge[1]
- 在adj_list[u-1]的末尾插入v-1
- 在adj_list[v-1]的末尾插入u-1
- value_list := 一個大小為n的新列表，初始化為0
- not_visited := 一個大小為i的新對映，其中i是adj_list中非空列表的數量
- 當not_visited不為空時，執行：
- 對於not_visited中的每個i，執行：
- value_list[i] := value_list[i] + values[i]
- 如果adj_list[i]的長度非零，則
- 從adj_list[adj_list[i, 0]]中刪除i
- value_list[adj_list[i, 0]] := value_list[adj_list[i, 0]] + value_list[i]
- 對於not_visited中的每個i，執行：
- 如果len(adj_list[i]) 和 len(adj_list[adj_list[i, 0]]) == 1，則
- not_visited := 一個包含adj_list[i, 0]的新列表
- 如果len(adj_list[i]) 和 len(adj_list[adj_list[i, 0]]) == 1，則
- 對於not_visited中的每個i，執行：
- return_val := |sum(values) - 2 * value_list[0]|
- 對於從1到n的i，執行：
- decision_val := |sum(values) - 2 * value_list[i]|
- 如果decision_val < return_val，則
- return_val := decision_val
- 返回return_val
示例
讓我們看看下面的實現以更好地理解：
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]))輸入
6, [[1, 2], [1, 3], [2, 4], [3, 5], [3, 6]], [10, 20, 10, 50, 10, 60]
輸出
0
更新於：2021年10月23日
瀏覽量：121
廣告