สมมติว่ามี n หลังคาเรือนในหมู่บ้าน เราต้องจัดหาน้ำให้ทุกหลังโดยการขุดบ่อน้ำและปั๊มท่อส่ง สำหรับแต่ละหลัง i เราสามารถขุดบ่อน้ำภายในได้ โดยค่าใช้จ่ายคือ wells[i] หรือดึงน้ำจากบ่อน้ำอื่นผ่านท่อ ค่าใช้จ่ายในการปูท่อระหว่างหลังคาเรือนกำหนดโดยอาร์เรย์ pipes โดย pipes[i] = [house1, house2, cost] แสดงค่าใช้จ่ายเชื่อม house1 และ house2 ท่อทำงานได้สองทิศทาง เราต้องหาค่าใช้จ่ายรวมต่ำสุดเพื่อจัดหาน้ำให้ทุกหลัง
เช่น n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]] ผลลัพธ์คือ 3
จากภาพแสดงค่าใช้จ่ายเชื่อมท่อ กลยุทธ์ที่ดีที่สุดคือขุดบ่อน้ำที่หลังแรก ค่า 1 และเชื่อมหลังอื่นๆ เข้ามา ค่า 2 รวมเป็น 3
วิธีแก้ (ใช้ Union-Find / Kruskal's Algorithm):
ฟังก์ชัน find(a): หา root parent พร้อม path compression
ฟังก์ชัน union(a,b): รวมเซต ถ้า root ต่างกัน
เพิ่ม "บ่อน้ำเสมือน" เป็นโหนด 0 เชื่อมกับแต่ละหลังคาเรือน ด้วยค่าใช้จ่าย wells[i]
รวม pipes และการเชื่อมบ่อน้ำ แล้วเรียงตามค่าใช้จ่าย
ใช้ Kruskal เลือก edge ที่ไม่ทำให้เกิด cycle รวมค่าใช้จ่าย
ตัวอย่างการใช้งาน
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 _ in range(n+1)]
for i in range(len(well)):
pipes.append([0, i+1, well[i]])
pipes = sorted(pipes, key=lambda v: v[2])
cost = 0
for i in pipes:
source, destination, temp = i[0], i[1], 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]]
เอาต์พุท
3
