โปรแกรมตรวจสอบการมีอยู่ของเส้นทางจำกัดความยาวขอบใน Python

สมมติว่าเรามีกราฟการถ่วงน้ำหนักแบบไม่มีทิศทางที่มี n โหนดโดยใช้หนึ่ง edgeList โดยที่ edgeList[i] มีพารามิเตอร์สามตัว (u, v, w) แสดงว่ามีเส้นทางจาก u ถึง v ซึ่งระยะห่างคือ w เรายังมีอาร์เรย์การสืบค้นอื่นที่การสืบค้น[i]มี (p, q, lim) แบบสอบถามนี้พยายามถามว่ามีเส้นทาง (โดยตรงหรือผ่านโหนดอื่น ๆ ) จาก p ถึง q ที่มีระยะทางน้อยกว่า lim เราต้องคืนค่าอาร์เรย์ที่มีผล True/False สำหรับแต่ละแบบสอบถาม

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น [จริง เท็จ จริง] เนื่องจากการไปจาก 1 เป็น 4 เราสามารถไปตามเส้นทาง 1 -> 3 -> 4 ด้วยราคา 11 อันที่สองเป็นเท็จเพราะเราไม่สามารถไปจาก 2 เป็น 3 โดยใช้น้อยกว่า 3 และอันสุดท้ายเป็นจริงเพราะเราสามารถไปจาก 1 ถึง 2 โดยใช้เส้นทาง 1 -> 3 -> 2 โดยมีค่าใช้จ่าย 14 ซึ่งน้อยกว่า 15

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

• parent :=รายการตั้งแต่ 0 ถึง n

• อันดับ :=รายการขนาด n+1 และเติม 0

• กำหนดฟังก์ชัน find() สิ่งนี้จะพาผู้ปกครอง x

• ถ้า parent[x] เหมือนกับ x แล้ว

  • ผลตอบแทน x

• parent[x] :=find(parent, parent[x])

• ส่งคืนพาเรนต์[x]

• กำหนดฟังก์ชัน union() นี่จะพาผู้ปกครอง a, b

• a :=find(parent, a)

• b :=find(parent, b)

• ถ้า a เหมือนกับ b แล้ว

  • กลับ

• ถ้า rank[a]

  • ผู้ปกครอง[a] :=b

• มิฉะนั้น เมื่อ rank[a]> rank[b] แล้ว

  • ผู้ปกครอง[b] :=a

• มิฉะนั้น

  • ผู้ปกครอง[b] :=a

  • อันดับ[a] :=อันดับ[a] + 1

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• จัดเรียง edgeList ตามพารามิเตอร์น้ำหนัก

• res :=อาร์เรย์ที่มีจำนวนการสืบค้นข้อมูลและเติมด้วย 0

• การสืบค้น :=รายการคู่ (i, ch) สำหรับแต่ละดัชนี i และค่า ch จากข้อความค้นหา

• จัดเรียงข้อความค้นหาตามพารามิเตอร์ขีดจำกัด

• ind :=0

• สำหรับแต่ละดัชนี i triplet (a, b, w) ในการสืบค้น ทำ

  • ในขณะที่ ind <ขนาดของ edgeList และ edgeList[ind, 2]

    • union(parent, edgeList[ind, 0])

    • ind :=ind + 1

  • res[i] :=find(parent, a) เหมือนกับ find(parent, b)

• ผลตอบแทน

ตัวอย่าง

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

def Solve(n, edgeList, query):parent =[i for i in range(n+1)] rank =[0 for i in range(n+1)] def find(parent, x):ถ้า parent[x] ==x:return x parent[x] =find(parent, parent[x]) ส่งคืน parent[x] def union(parent, a, b):a =find(parent, a) b =find (พาเรนต์, b) ถ้า a ==b:return if rank[a]  rank[b]:parent[b] =a else:parent[ b] =อันดับ[a] +=1 edgeList.sort(key =lambda x:x[2]) res =[0] * len(queries) query =[[i, ch] for i, ch in enumerate( ข้อความค้นหา)] query.sort(key =lambda x:x[1][2]) ind =0 for i, (a, b, w) ในเคียวรี:while ind  
อินพุต
 <ก่อนหน้า>4, [(1,2,16),(1,3,8),(2,4,3),(2,3,6),(4,3,3)],[(1 ,4,12),(2,3,3),(1,2,15)]

ผลลัพธ์

[จริง เท็จ จริง]