Pythonですべての都市の可能な最大人口を見つけるためのプログラム

N個のノードとN-1個のエッジを持つツリーとして表される国を考えてみます。これで、各ノードは町を表し、各エッジは道路を表します。サイズN-1のソースと宛先の番号の2つのリストがあります。彼らによると、i番目の道路はsource[i]とdest[i]を接続しています。そして、道路は双方向です。サイズNの人口と呼ばれる別の数のリストもあります。ここで、population[i]はi番目の町の人口を表します。いくつかの町を都市にアップグレードしようとしています。ただし、2つの都市が互いに隣接していてはならず、町に隣接するすべてのノードが都市である必要があります（すべての道路が町と都市を接続している必要があります）。したがって、すべての都市の可能な最大人口を見つける必要があります。

したがって、入力が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をマーク
• ans：=0
• choiceがtrueの場合、
  • ans：=ans + Population [x]
• adj [x]のネイバーごとに、
  • ans：=ans + dfs（neighbor、inverse of Choose）
• 回答を返す
• メインの方法から次の手順を実行します。
• 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