Pythonで村の配水を最適化する

村にn軒の家があるとしましょう。井戸を作ったり、パイプを敷いたりして、すべての家に水を供給しなければなりません。家iごとに、その中に井戸を建設するか、建設費は井戸[i]になるか、別の井戸からそこに水をパイプで送ることができます。家の間にパイプを敷設するためのコストは、アレイパイプによって与えられます。ここで、各パイプ[i]は[house1、house2、cost]であり、パイプを使用してhouse1とhouse2を接続するコストを表します。これらの接続は双方向です。すべての家に水を供給するための最小の総費用を見つける必要があります。

したがって、入力がn =3、wells =[1,2,2]、pipes =[[1,2,1]、[2,3,1]]の場合、出力は3

上の画像のように、パイプを使用して家を接続するコストを示しています。最善の戦略は、コスト1の最初の家に井戸を建設し、コスト2で他の家をそれに接続して、合計コストが3になるようにすることです。

これを解決するには、次の手順に従います-

• 関数find（）を定義します。これには

  かかります

• parent [a]が-1と同じ場合、

  • を返す

• parent [a]：=find（parent [a]）

• 親を返す[a]

• 関数union（）を定義します。これにはa、b

  がかかります

• parent_a：=find（a）

• parent_b：=find（b）

• parent_aがparent_bと同じ場合、

  • Trueを返す

• parent [parent_b]：=parent_a

• Falseを返す

• メインの方法から、次のようにします-

• 親：=サイズn + 1のリストを作成し、これに-1を入力します

• カウンター：=0

• 0からウェルのサイズまでの範囲のiの場合、実行します

  • パイプの端に[0、i + 1、well[i]]を挿入します

  • カウンター：=カウンター+ 1

• コストに基づいてパイプ配列を並べ替える

• コスト：=0

• パイプ内の各iについて、実行します

  • ソース：=i [0]

  • 宛先：=i [1]

  • temp：=i [2]

  • union（source、destination）がfalseの場合、

    • コスト：=コスト+温度

• 返品費用

理解を深めるために、次の実装を見てみましょう-

例

class Solution(object):
   def find(self, a):
      if self.parent[a] == -1:
         return a
      self.parent[a] = self.find(self.parent[a])
      return self.parent[a]
   def union(self,a,b):
      parent_a = self.find(a)
      parent_b = self.find(b)
      if parent_a == parent_b:
         return True
      self.parent[parent_b] = parent_a
      return False
   def minCostToSupplyWater(self, n, well, pipes):
      self.parent = [-1 for i in range(n+1)]
      counter = 0
      for i in range(len(well)):
         pipes.append([0,i+1,well[i]])
         counter+=1
      pipes = sorted(pipes,key=lambda v:v[2])
      cost = 0
      for i in pipes:
         #print(i)
         source = i[0]
         destination = i[1]
         temp = i[2]
         if not self.union(source,destination):
            cost+=temp
      return cost

ob = Solution()
print(ob.minCostToSupplyWater(3, [1,2,2], [[1,2,1],[2,3,1]]))

入力

3, [1,2,2], [[1,2,1],[2,3,1]]

出力

1