Python程式：查詢所有城市的最大可能人口

假設一個國家用一個具有N個節點和N-1條邊的樹表示。每個節點代表一個城鎮，每條邊代表一條道路。我們有兩個大小為N-1的數字列表source和dest。根據它們，第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]，則輸出將為15，因為我們可以將城市0、2和4升級，以獲得6 + 4 + 5 = 15的人口。

為了解決這個問題，我們將遵循以下步驟：

  • adj := 使用source和dest建立圖的鄰接表
  • 定義一個函式dfs()。它將接收x, choose作為引數
  • 如果x已被訪問，則
    • 返回0
  • 標記x為已訪問
  • ans := 0
  • 如果choose為真，則
    • ans := ans + population[x]
  • 對於adj[x]中的每個鄰居，執行：
    • ans := ans + dfs(neighbor, 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

更新於：2020年12月3日

563 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告