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

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

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

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

• adj := स्रोत और डेस्ट का उपयोग करके ग्राफ की एडजेसेंसी सूची बनाएं
• dfs() फ़ंक्शन परिभाषित करें। यह x, choose लेगा
• यदि x देखा गया है, तो
  • 0 लौटाएं
• x को देखा गया के रूप में चिह्नित करें
• ans := 0
• यदि choose सत्य है, तो
  • ans := ans + population[x]
• adj[x] में प्रत्येक पड़ोसी के लिए, करें
  • ans := ans + dfs(पड़ोसी, choose का व्युत्क्रम)
• ans लौटाएं
• मुख्य मेथड से निम्नलिखित करें:
• 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