पायथन में सभी शहरों की अधिकतम संभव जनसंख्या खोजने का कार्यक्रम

उस देश पर विचार करें जिसे एन नोड्स और एन-1 किनारों वाले पेड़ के रूप में दर्शाया गया है। अब प्रत्येक नोड एक शहर का प्रतिनिधित्व करता है, और प्रत्येक किनारा एक सड़क का प्रतिनिधित्व करता है। हमारे पास संख्या स्रोत और नियति आकार N-1 की दो सूचियाँ हैं। उनके अनुसार i-th सड़क स्रोत [i] को गंतव्य [i] से जोड़ती है। और सड़कें द्विदिश हैं। हमारे पास संख्याओं की एक अन्य सूची भी है जिसे N आकार की जनसंख्या कहा जाता है, जहाँ जनसंख्या [i] i-वें शहर की जनसंख्या का प्रतिनिधित्व करती है। हम कुछ शहरों को शहरों में अपग्रेड करने का प्रयास कर रहे हैं। लेकिन कोई भी दो शहर एक दूसरे से सटे नहीं होने चाहिए और एक कस्बे से सटे हर नोड एक शहर होना चाहिए (हर सड़क एक शहर और एक शहर को जोड़ती है)। इसलिए हमें सभी शहरों की अधिकतम संभव आबादी का पता लगाना होगा।

इसलिए, यदि इनपुट स्रोत की तरह है =[2, 2, 1, 1] डेस्ट =[1, 3, 4, 0] जनसंख्या =[6, 8, 4, 3, 5], तो आउटपुट 15 होगा, जैसा कि हम 6 + 4 + 5 =15 की जनसंख्या प्राप्त करने के लिए शहरों 0, 2, और 4 को अपग्रेड कर सकते हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• adj :=स्रोत और नियति का उपयोग करके ग्राफ़ की आसन्न सूची बनाएं
• एक फ़ंक्शन को परिभाषित करें dfs() । इसमें x लगेगा, चुनें
• यदि x दिखाई देता है, तो
  • वापसी 0
• x को देखा के रूप में चिह्नित करें
• उत्तर:=0
• अगर चुनना सही है, तो
  • उत्तर:=उत्तर + जनसंख्या[x]
• adj[x] में प्रत्येक पड़ोसी के लिए, करें
  • Ans :=ans + dfs(पड़ोसी, पसंद का विलोम)
• वापसी उत्तर
• मुख्य विधि से निम्न कार्य करें:
• x :=dfs(0, True)
• अधिकतम x लौटाएं और ((जनसंख्या का योग) - x)

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

उदाहरण

from collections import defaultdict
class Solution:
   def solve(self, source, dest, population):
      adj = defaultdict(list)
      for a, b in zip(source, dest):
         adj[a].append(b)
         adj[b].append(a)

      seen = set()

      def dfs(x, choose):
         if x in seen:
            return 0
         seen.add(x)
         ans = 0
         if choose:
            ans += population[x]
         for neighbor in adj[x]:
            ans += dfs(neighbor, not choose)
         return ans

      x = dfs(0, True)
      return max(x, sum(population) - x)
     
ob = Solution()
source = [2, 2, 1, 1]
dest = [1, 3, 4, 0]
population = [6, 8, 4, 3, 5]
print(ob.solve(source, dest, population))

इनपुट

[2, 2, 1, 1], [1, 3, 4, 0], [6, 8, 4, 3, 5]

आउटपुट

15