Chương trình tìm ra chi phí tối thiểu để người dân có thể tiếp cận thị trường bằng Python

Giả sử, có n số thành phố và m đường nối các thành phố. Công dân của người dân cần thị trường nơi họ có thể mua hàng hóa của họ. Bây giờ, không có chợ trong các thành phố và các con đường giữa các thành phố đang được xây dựng. Có thể xây dựng đường hai chiều giữa hai thành phố nếu (i) Thành phố có chợ; (ii) Có thể đến thăm các thành phố bằng con đường nơi có chợ. Chi phí xây dựng một con đường là x, và xây dựng một khu chợ là y và chúng đã cho. Chúng tôi phải tìm ra chi phí tối thiểu để cung cấp khả năng tiếp cận thị trường cho người dân của mỗi thành phố. Mảng 'thành phố' chứa thông tin về các thành phố về các thành phố có thể được kết nối bằng đường bộ.

Vì vậy, nếu đầu vào là n =4, m =3, x =1, y =2, thành phố =[[1, 2], [2, 3], [3, 4]], thì đầu ra sẽ là 4.

Ở đây, chúng ta có thể thấy bốn thành phố 1, 2, 3 và 4. Nếu một khu chợ được xây dựng thì một thành phố thứ 1 và hai con đường nữa được xây dựng từ (1, 4) đến (1,3) thì tổng chi phí sẽ là 2 + 1 + 1 =4. Đây là chi phí tối thiểu.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nếu x <=y, thì
  • trả về n * x
• nếu không,
  • adj_list:=một bản đồ chứa các danh sách dưới dạng các phần tử
  • đối với mỗi thành phố trong các thành phố, hãy thực hiện
    • city1:=city [0]
    • city2:=city [1]
    • chèn city2 vào cuối adj_list [city1]
    • chèn city1 vào cuối adj_list [city2]
  • temp:=một danh sách mới có kích thước (n + 1) được khởi tạo với giá trị True
  • giá trị:=0
  • dq:=một hàng đợi kết thúc kép
  • đối với cur trong phạm vi 1 đến n + 1, thực hiện
    • nếu temp [cur] khác 0, thì
      • giá trị:=value + x
      • chèn cur vào cuối cùng bên phải của dq
      • temp [cur]:=False
      • trong khi dq không trống, hãy làm
      • đối với mỗi i adj_list [phần tử ngoài cùng bên trái được trích xuất của dq], hãy thực hiện
        • nếu temp [i] khác 0, thì
          • chèn i vào cuối cùng bên phải của dq
          • temp [i]:=False
          • giá trị:=value + y
  • giá trị trả về

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

from collections import defaultdict, deque
def solve(n, m, x, y, cities):
   if x <= y:
      return n * x
   else:
      adj_list = defaultdict(list)
      for city in cities:
         city1 = city[0]
         city2 = city[1]
         adj_list[city1].append(city2)
         adj_list[city2].append(city1)
      temp = [True] * (n + 1)
      value = 0
      dq = deque()
      for cur in range(1, n + 1):
         if temp[cur]:
            value += x
            dq.append(cur)
            temp[cur] = False
            while dq:
               for i in adj_list[dq.popleft()]:
                  if temp[i]:
                     dq.append(i)
                     temp[i] = False
                     value += y
      return value

print(solve(4, 3, 1, 2, [[1, 2], [2, 3], [3, 4]]))

Đầu vào

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

Đầu ra

4