पायथन में सब-ट्री के नोड मानों के योग से न्यूनतम मान खोजने का प्रोग्राम

मान लीजिए, हमारे पास एक ट्री है जिसके सभी नोड्स 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 में प्रत्येक edge के लिए, करें
- u := edge[0]
- v := edge[1]
- v-1 को adj_list[u-1] के अंत में डालें
- u-1 को adj_list[v-1] के अंत में डालें
value_list := 0s से आरंभ की गई आकार n की एक नई सूची
not_visited := आकार i का एक नया मैप, जहां i, adj_list में गैर-खाली सूचियों की संख्या है
जब तक not_visited खाली नहीं है, करें
- not_visited में प्रत्येक i के लिए, करें
  - value_list[i] := value_list[i] + values[i]
  - यदि (adj_list[i]) की लंबाई शून्येतर है, तो
    - i को adj_list[adj_list[i, 0]] से हटाएं
    - 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] वाली एक नई सूची
return_val := |sum(values) - 2 * value_list[0]|
i को 1 से n तक की रेंज में, करें
- 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]