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

สมมติว่ามีเมืองจำนวน n และถนน m ที่เชื่อมระหว่างเมือง พลเมืองของประชาชนต้องการตลาดที่พวกเขาสามารถซื้อสินค้าได้ ขณะนี้ ไม่มีตลาดในเมือง และถนนระหว่างเมืองอยู่ระหว่างการก่อสร้าง ถนนสองทางสามารถสร้างขึ้นระหว่างสองเมืองได้ ถ้า (i) เมืองนี้มีตลาด (ii) สามารถเยี่ยมชมเมืองได้ตามถนนที่มีตลาด ค่าใช้จ่ายในการสร้างถนนคือ x และการสร้างตลาดคือ y และจะได้รับ เราต้องหาต้นทุนขั้นต่ำในการเข้าถึงตลาดให้กับพลเมืองของแต่ละเมือง 'เมือง' ของอาเรย์ประกอบด้วยข้อมูลเกี่ยวกับเมืองที่เมืองต่างๆ สามารถเชื่อมต่อด้วยถนนได้

ดังนั้น หากอินพุตเป็น n =4, m =3, x =1, y =2, เมือง =[[1, 2], [2, 3], [3, 4]] ผลลัพธ์จะเป็น 4.

ในที่นี้ เราจะเห็นสี่เมือง 1, 2, 3 และ 4 หากตลาดสร้างเมืองที 1 และถนนอีกสองแห่งถูกสร้างขึ้นระหว่าง (1, 4) และ (1,3) ค่าใช้จ่ายทั้งหมดจะเป็น 2 + 1 +1 =4 นี่คือต้นทุนขั้นต่ำ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ถ้า x <=y แล้ว
  • ส่งคืน n * x
• มิฉะนั้น
  • adj_list :=แผนที่ที่มีรายการเป็นองค์ประกอบ
  • สำหรับแต่ละเมืองในเมือง ทำ
    • city1 :=เมือง[0]
    • city2 :=เมือง[1]
    • แทรก city2 ที่ส่วนท้ายของ adj_list[city1]
    • แทรก city1 ที่ส่วนท้ายของ adj_list[city2]
  • temp :=รายการขนาดใหม่ (n + 1) เริ่มต้นด้วยค่า True
  • ค่า :=0
  • dq :=คิวที่สิ้นสุดสองครั้ง
  • สำหรับ cur ในช่วง 1 ถึง n + 1 ทำ
    • ถ้า temp[cur] ไม่ใช่ศูนย์ แล้ว
      • ค่า :=ค่า + x
      • แทรก cur ที่ปลายขวาสุดของ dq
      • อุณหภูมิ[cur] :=เท็จ
      • ในขณะที่ dq ไม่ว่างเปล่า ให้ทำ
      • สำหรับแต่ละ i adj_list[แยกองค์ประกอบซ้ายสุดของ dq] ทำ
        • ถ้า temp[i] ไม่ใช่ศูนย์ แล้ว
          • แทรก i ที่ปลายขวาสุดของ dq
          • อุณหภูมิ[i] :=เท็จ
          • ค่า :=ค่า + y
  • คืนค่า

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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]]))

อินพุต

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

ผลลัพธ์

4