पायथन में उप-पेड़ों के नोड मानों के योग से न्यूनतम मान ज्ञात करने का कार्यक्रम

मान लीजिए, हमारे पास एक पेड़ है जिसके सभी नोड्स 1 से n तक गिने गए हैं। प्रत्येक नोड में एक पूर्णांक मान होता है। अब यदि हम पेड़ से एक किनारा हटाते हैं, तो दो उप-वृक्षों के नोड मानों के योग में अंतर न्यूनतम होना चाहिए। हमें ऐसे उप-वृक्षों के बीच न्यूनतम अंतर का पता लगाना और वापस करना होगा। पेड़ हमें किनारों के संग्रह के रूप में दिया जाता है, और नोड्स के मान भी प्रदान किए जाते हैं।

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

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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]