在Python中查找所有城市的最大可能人口的程序

考虑一个由N个节点和N-1条边表示的国家树。现在每个节点表示一个城镇，每条边表示一条道路。我们有两个大小为N-1的数字列表source和dest。根据它们，第i条道路连接源[i]到目的地[i]。而且，这两条道路是双向的。我们还有另一个名为人口的数字列表，大小为N，其中人口[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：通过使用source和dest进行图的邻接表
• 定义函数dfs()。这将要求x，选择
• 如果x已看到，则
  • 返回0
• 标记x为已看到
• 答案= 0
• 如果选择是true，则
  • 答案=答案+人口[x]
• 对于每个邻居在adj[x]中，执行
  • 答案=答案+ 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