讓我們有一棵樹，它的邊緣由價格評估，價格是一些整數。我們將所有邊的價格總和稱為樹的價格。如果我們通過洗掉一條邊來切割一棵樹，它將分成兩棵樹。我們稱之為降價的最高價格。我們的任務是找到最便宜的切割。
輸出應該是一個數字，即切割的最低價格。
例子：
輸入：
5
1 4 1
1 2 1
2 3 3
4 5 2
第一個數字是頂點的數量。之后，我們有頂點數 - 1 行。行中的前兩個數字是頂點之間的連接，因此1 4表示 1 和 4 是連接的。行中的最后一個數字是邊緣的“價格”。
所以在這種情況下，輸出應該是 3，因為如果我們洗掉 2 和 1 之間的邊，我們將得到兩個子樹，邊分別是 3 和 3（它們的價格）。
1
/ \
2 4
\3 \2
3 5
（曲線圖，/并且\是邊數是頂點，數字到下一個/和\是邊緣的價格）
我考慮了一段時間，但不知道執行此操作的正確演算法。
我寫的基本程式：
number_of_vertices = int(input())
edges = []
price = []
for i in range(number_of_vertices):
u, v, c = input().split()
edges.append([int(u),int(v)])
price.append(int(c))
我想過遍歷每一條邊，洗掉它們然后計算，但我不知道如何實作它。
所以我制作了一個鄰居字典和一個 find_path 演算法來查找兩個頂點之間是否存在邊：
from collections import defaultdict
def find_path(graph, start, end, path=[]):
path = path [start]
if start == end:
return True
if start not in graph:
return False
for node in graph[start]:
if node not in path:
newpath = find_path(graph, node, end, path)
if newpath: return True
return False
number_of_vertices = int(input())
edges = []
price = []
for i in range(number_of_vertices - 1):
u, v, c = input().split()
edges.append([int(u),int(v)])
price.append(int(c))
graph = defaultdict(set)
for vertices in edges:
graph[vertices[0]].add(vertices[1])
graph[vertices[1]].add(vertices[0])
print(find_path(graph, 1, 3)) #this is just to make sure it works
print(dict(graph)) #this too
uj5u.com熱心網友回復：
首先，計算一下這棵樹的總價，比方說totalCost。現在我們將遍歷樹并嘗試洗掉每條邊，看看砍價是否最低。
對于每個節點，我們可以計算其子樹的價格。如果我們移除一個子樹的邊并且我們知道其子樹的成本，那么我們可以通過減去子樹的價格和要移除的邊成本輕松找到剩余樹的成本。假設我們正在移除Uto的邊緣VcostX和 cost of subtree Vis costOfSubTree。那么剩下的樹的成本是
costOfRemainingTree = totalCost - costOfSubTree - X
現在我們有了從 U 到 V 移除邊緣后兩棵樹的成本。現在我們有最大的成本（切割價格）并將其與我們迄今為止找到的最小切割進行比較。
這里總成本是 21。子樹 2 的成本是 12。現在如果我們從 1-2 中洗掉邊，我們將有兩棵樹。一棵是成本為 12 的子樹 2，另一棵樹的成本是 (21 - 12 - 4) = 5，這里 4 是 1 - 2 的邊成本。現在我們有兩棵成本為 5 和 12 的樹，所以這里是 Cut費用為 12。
通過這種方式，我們可以嘗試每一條邊，并盡量減少答案。如果我們知道要洗掉哪條邊，我們可以很容易地找到兩棵樹的節點。
uj5u.com熱心網友回復：
LOOP over nodes
Calculate cost of subtree from node
LOOP over links
Calculate cut cost of link max( subtree cost of deepest node, tree cost - subtree cost - link cost )
If cut cost less than previous cheapest, replace cheapest
Output cheapest found
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/408345.html
標籤：
下一篇：嘗試使用Map.values().parallelStream().forEach(list->list.sort(comarator))但得到錯誤：“比較方法違反了它的一般合同！”