程序以python查找所有城市的最大可能人口

考虑一个表示为具有N个节点和N-1边缘的树的国家。现在，每个节点代表一个城镇，每个边沿代表一条道路。我们有两个数字列表，分别是大小为N-1的数字源和目标。根据他们，第i条道路将source [i]连接到dest [i]。道路是双向的。我们还有另一个数字列表，称为人口规模N，其中，人口[i]代表第i个镇的人口。我们正在尝试将一些城镇升级为城市。但是，不应有两个城市彼此相邻，并且与城镇相邻的每个节点都应该是一个城市（每条道路都必须连接一个城镇和一个城市）。因此，我们必须找到所有城市的最大可能人口。

因此，如果输入类似于source = [2，2，1，1] dest = [1，3，4，0]人口= [6，8，4，4，3，5]，那么输出将为15，因为我们可以将城市0、2和4升级为6 + 4 + 5 = 15的人口。

为了解决这个问题，我们将遵循以下步骤-

• adj：=通过使用source和dest创建图的邻接表

• 定义一个功能dfs()。这将需要x，选择

• 如果看到x，则

• 返回0

• 将x标记为可见

• 回答：= 0

• 如果选择为真，则

• ans：= ans +人口[x]

• 对于adj [x]中的每个邻居，执行

• ans：= ans + dfs（邻居，选择逆）

• 返回ans

• 从主要方法执行以下操作：

• x：= dfs（0，真）

• 返回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