โปรแกรมหาต้นทุนขั้นต่ำเพื่อให้พลเมืองเข้าถึงตลาดได้ใน Python

มี n เมือง m ทางเชื่อม ต้องสร้างตลาดและถนน ให้ทุกเมืองเข้าถึงตลาดได้ ค่าสร้างถนน x ค่าสร้างตลาด y หาต้นทุนต่ำสุด

ตัวอย่าง: n=4, m=3, x=1, y=2, cities=[[1,2],[2,3],[3,4]] → 4

ขั้นตอนการแก้ปัญหา

1. หาก x ≤ y: สร้างถนนเชื่อมทุกเมือง ต้นทุน = n * x
2. มิฉะนั้น: หา connected components ของกราฟ สำหรับแต่ละ component สร้างตลาด 1 แห่ง และถนนเชื่อมภายใน component (n_component - 1 ถนน) ต้นทุน = components * y + (n - components) * x

ตัวอย่างโค้ด Python

from collections import defaultdict, deque

def solve(n, m, x, y, cities):
    if x <= y:
        return n * x
    adj = defaultdict(list)
    for u, v in cities:
        adj[u].append(v)
        adj[v].append(u)
    visited = [False] * (n + 1)
    components = 0
    for i in range(1, n + 1):
        if not visited[i]:
            components += 1
            dq = deque([i])
            visited[i] = True
            while dq:
                u = dq.popleft()
                for v in adj[u]:
                    if not visited[v]:
                        visited[v] = True
                        dq.append(v)
    return components * y + (n - components) * x

# ทดสอบ
print(solve(4, 3, 1, 2, [[1, 2], [2, 3], [3, 4]]))  # ผลลัพธ์: 4

อินพุตตัวอย่าง

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

เอาต์พุตตัวอย่าง

4