한 마을에 n개의 집이 있다고 가정합니다. 우리는 우물을 만들고 파이프를 설치하여 모든 집에 물을 공급해야 합니다. 각 집 i에 대해, 우리는 그 안에 우물을 지을 수 있고, 건축 비용은 우물[i]이 될 것입니다. 또는 다른 우물에서 물을 파이프로 보낼 수 있습니다. 집 사이에 파이프를 설치하는 비용은 배열 파이프로 표시되며 각 파이프[i]는 [house1, house2, cost]는 파이프를 사용하여 house1과 house2를 연결하는 비용을 나타냅니다. 이러한 연결은 양방향입니다. 우리는 모든 집에 물을 공급하기 위한 최소 총 비용을 찾아야 합니다.
따라서 입력이 n =3, wells =[1,2,2], 파이프 =[[1,2,1],[2,3,1]]인 경우 출력은 3
위의 이미지에서와 같이 파이프를 사용하여 주택을 연결하는 비용을 보여줍니다. 가장 좋은 전략은 비용이 1인 첫 번째 집에 우물을 만들고 비용 2로 다른 집들을 연결하여 총 비용이 3이 되도록 하는 것입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
find() 함수를 정의합니다. 시간이 걸립니다
-
부모[a]가 -1과 같으면
-
반환
-
-
부모[a] :=찾기(부모[a])
-
부모 반환[a]
-
함수 union()을 정의합니다. 시간이 걸립니다,b
-
parent_a :=찾기(a)
-
parent_b :=찾기(b)
-
parent_a가 parent_b와 같으면
-
참을 반환
-
-
부모[parent_b] :=parent_a
-
거짓을 반환
-
주요 방법에서 다음을 수행하십시오 -
-
parent :=크기가 n + 1인 목록을 만들고 -1로 채웁니다.
-
카운터 :=0
-
범위 0에서 우물 크기까지의 i에 대해
-
파이프 끝에 [0, i+1, well[i]] 삽입
-
카운터 :=카운터 + 1
-
-
비용에 따라 파이프 배열 정렬
-
비용 :=0
-
파이프의 각 i에 대해
-
출처 :=i[0]
-
목적지 :=i[1]
-
온도 :=i[2]
-
Union(source,destination)이 거짓이면
-
비용 :=비용 + 온도
-
-
-
반품 비용
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
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