Chương trình tìm ra con đường tối thiểu để gửi tất cả các chữ cái bằng Python

Giả sử có n thành phố và được kết nối với n -1 đường. Một thành phố có thể được đến thăm từ bất kỳ thành phố nào khác. Bây giờ hệ thống bưu điện của các thành phố chuyển phát k bức thư mỗi ngày. Điểm đến của lá thư có thể là bất kỳ thành phố nào trong số k thành phố khác nhau. Một nhân viên bưu điện phải chuyển tất cả các bức thư đến địa chỉ của họ mỗi ngày. Chúng tôi sẽ phải tìm ra khoảng cách tối thiểu mà người lao động phải đi để chuyển tất cả các bức thư. Nhân viên có thể bắt đầu từ bất kỳ thành phố nhất định nào.

Vì vậy, nếu đầu vào giống như

và các bức thư phải được chuyển đến ở các thành phố (delv) 1, 2 và 4; thì đầu ra sẽ là 4.

Công nhân có thể bắt đầu giao hàng từ các thành phố 1, 2 hoặc 4. Nếu công nhân bắt đầu từ thành phố 1, thì đường đi sẽ là 1-> 2-> 4, ngược lại trong trường hợp thành phố 4; 4-> 2-> 1. Tổng chi phí sẽ là 1 + 3 =4. Nếu anh ta bắt đầu từ thành phố 2, chi phí sẽ lớn hơn hai thành phố kia.

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

• Xác định một hàm depth_search (). Điều này sẽ lấy nút, p
  • d1:=-infinity
  • d2:=-infinity
  • đối với mỗi cặp x, y trong adj_list [node], thực hiện
    • nếu x không giống p, thì
      • d1:=tối đa của (d1, depth_search (x, node) + y)
      • nếu d1> d2, thì
        • hoán đổi các giá trị của d2 và d1
      • ti [node]:=ti [node] + ti [x]
      • nếu 0
      • SUM:=SUM + y
  • nếu d1> 0, thì
    • MAX:=tối đa trong tổng số (MAX, d1 + d2)
  • nếu d2> 0 và tj [node] khác 0, thì
    • MAX:=tối đa là (MAX, d2)
  • nếu tj [node] khác 0, thì
    • d2:=max (0, d2)
  • trả về d2

Ví dụ

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

 import sysfrom math import inf dưới dạng INFsys.setrecursionlimit (10 ** 5 + 5) def depth_search (node, p):global SUM, MAX d1 =-INF d2 =-INF cho x, y trong adj_list [node]:if x! =p:d1 =max (d1, depth_search (x, node) + y) if d1> d2:d1, d2 =d2, d1 ti [node] + =ti [x] if 0  0:MAX =max (MAX, d1 + d2) nếu d2> 0 và tj [nút]:MAX =max (MAX, d2) nếu tj [nút]:d2 =max ( 0, d2) trả về d2def giải quyết (nút, delv, đường):k toàn cục, ti, tj, adj_list, SUM, MAX k =len (delv) adj_list ={} ti =[0] * (nút + 5) tj =[0] * (node ​​+ 5) for i in delv:ti [i] =tj [i] =1 for item in the road:x, y, c =map (int, item) if x not in adj_list:adj_list [ x] =[] nếu y không có trong adj_list:adj_list [y] =[] adj_list [x] .append ([y, c]) adj_list [y] .append ([x, c]) SUM =0 MAX =0 deep_search (1,1) trả về SUM * 2 - MAXprint (solv e (5, [1, 2, 4], [(1,2,1), (2,3,2), (2,4,3), (1,5,1)]))  
 Đầu vào 
 
 5, [1, 2, 4], [(1,2,1), (2,3,2), (2,4,3), (1,5,1)] 
 
 Đầu ra 
 
 4