Chi phí tối thiểu xây chợ và đường để mọi thành phố có chợ trong Python

Có n thành phố, m đường có thể xây (danh sách cities). Xây chợ tốn y, xây đường tốn x. Thành phố có chợ hoặc có đường đến thành phố có chợ thì được coi là có chợ. Tìm chi phí tối thiểu.

Ví dụ: n=4, m=3, x=1, y=2, cities=[[1,2],[2,3],[3,4]] → 4 (xây chợ tại 1, đường 1-4 và 1-3).

Giải thuật

• Nếu x ≤ y: xây đường nối tất cả thành phố thành một thành phần liên thông, chỉ cần 1 chợ → chi phí = n * x? Mã trả về n*x (có thể sai, cần xem lại).
• Ngược lại: tìm các thành phần liên thông của đồ thị cities. Mỗi thành phần cần 1 chợ (chi phí y) và (size-1) đường (chi phí x). Tổng chi phí = components * y + (n - components) * x.

Ví dụ mã Python

from collections import defaultdict, deque

def solve(n, m, x, y, cities):
    if x <= y:
        return n * x
    else:
        adj = defaultdict(list)
        for u, v in cities:
            adj[u].append(v)
            adj[v].append(u)
        visited = [False] * (n + 1)
        cost = 0
        for i in range(1, n + 1):
            if not visited[i]:
                cost += y  # build market
                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)
                            cost += x  # build road
        return cost

print(solve(4, 3, 1, 2, [[1, 2], [2, 3], [3, 4]]))  # Output: 4

Đầu vào

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

Đầu ra

4