পাইথনে সিটি আপগ্রেড করে সর্বোচ্চ জনসংখ্যা বের করার প্রোগ্রাম

একটি দেশকে N নোড ও N-1 এজ দিয়ে একটি ট্রি হিসেবে রিপ্রেজেন্ট করা হয়েছে। প্রতিটি নোড একটি টাউন, এবং প্রতিটি এজ একটি রোড। আমাদের দুটি লিস্ট আছে source এবং dest আকার N-1। এ অনুযায়ী i-তম রোড source[i]-কে dest[i]-এর সাথে সংযুক্ত করে। রোডগুলো বাইডিরেকশনাল। আরেকটি লিস্ট population আকার N, যেখানে population[i] i-তম টাউনের জনসংখ্যা। আমরা কিছু টাউনকে সিটিতে আপগ্রেড করতে চাই। কিন্তু কোনো দুটি সিটি একে অপরের পাশে থাকতে পারবে না এবং টাউনের পাশের সব নোড সিটি হতে হবে (প্রতিটি রোড একটি টাউন ও একটি সিটি কানেক্ট করতে হবে)। আমাদের সকল সিটির সর্বোচ্চ জনসংখ্যা বের করতে হবে।

তাই, ইনপুট যদি source = [2, 2, 1, 1], dest = [1, 3, 4, 0], population = [6, 8, 4, 3, 5] হয়, তবে আউটপুট হবে ১৫, কারণ সিটি ০, ২, এবং ৪ আপগ্রেড করলে জনসংখ্যা ৬ + ৪ + ৫ = ১৫ হয়।

সমাধানের ধাপগুলো:

adj := source ও dest ব্যবহার করে গ্রাফের অ্যাডজেসেন্সি লিস্ট তৈরি করুন
dfs() ফাংশন ডিফাইন করুন। এটি x, choose নিবে
যদি x সিন হয়, তবে
- ০ রিটার্ন করুন
x কে সিন হিসেবে মার্ক করুন
ans := 0
যদি choose ট্রু হয়, তবে
- ans := ans + population[x]
প্রতিটি neighbor ইন adj[x] এর জন্য, করুন
- ans := ans + dfs(neighbor, not choose)
ans রিটার্ন করুন
মেইন মেথড থেকে করুন:
- x := dfs(0, True)
- max(x, sum(population) - 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]