สมมติว่าเราได้รับกราฟที่มีจุดยอด n จุดที่มีตัวเลข 0 ถึง n - 1 กราฟไม่มีทิศทางและขอบแต่ละด้านมีน้ำหนัก กราฟสามารถมีตุ้มน้ำหนักได้สามประเภท และตุ้มน้ำหนักแต่ละชนิดแสดงถึงงานเฉพาะ มีคนสองคนที่สามารถสำรวจกราฟได้ คือ แจ็คและเคซี่ย์ แจ็คสามารถข้ามกราฟได้หากขอบมีน้ำหนัก 1, เคซี่ย์สามารถข้ามกราฟได้หากมีน้ำหนัก 2 และทั้งคู่สามารถข้ามกราฟได้หากมีน้ำหนักขอบ 3 เราต้องลบขอบใดๆ ที่จำเป็นเพื่อให้กราฟสามารถข้ามผ่านได้ทั้งคู่ แจ็คและเคซี่ย์ เราคืนค่าจำนวนขอบที่จะลบออกเพื่อให้ข้ามผ่านได้ หรือเราจะคืนค่า -1 หากไม่สามารถให้ข้ามผ่านได้
ดังนั้นหากอินพุตเป็นแบบ
และ n =5; จากนั้นผลลัพธ์จะเป็น -1
กราฟไม่สามารถสำรวจได้ทั้งคู่โดยการลบขอบ ดังนั้น คำตอบคือ -1
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน find() การดำเนินการนี้จะใช้เวลา
-
ถ้า val ไม่เหมือนกับ root[val] แล้ว
-
root[val] :=find(root[val])
-
-
คืนค่ารูท[val]
-
-
กำหนดฟังก์ชัน union() นี่จะใช้เวลา val1, val2
-
val1:=find(val1)
-
val2 :=find(val2)
-
ถ้า val1 เหมือนกับ val2 แล้ว
-
คืนค่า 0
-
-
รูท[val1] :=val2
-
กลับ 1
-
-
res :=0
-
edge1 :=0
-
edge2 :=0
-
root :=รายการใหม่จากช่วง 0 ถึง n + 1
-
สำหรับแต่ละขอบ (u, v) และน้ำหนักของมันคือ e ทำ
-
ถ้าคุณเหมือนกับ 3 แล้ว
-
ถ้ายูเนี่ยน (v, w) ไม่ใช่ศูนย์ ดังนั้น
-
edge1 :=edge1 + 1
-
edge2 :=edge2 + 1
-
-
มิฉะนั้น
-
res :=res + 1
-
-
-
-
root0 :=root[จากดัชนี 0 ถึงจุดสิ้นสุด]
-
สำหรับแต่ละขอบ (u, v) และน้ำหนักของมันคือ e ทำ
-
ถ้าคุณเหมือนกับ 1 แล้ว
-
ถ้ายูเนี่ยน (v, w) ไม่ใช่ศูนย์ ดังนั้น
-
edge1 :=edge1 + 1
-
-
มิฉะนั้น
-
res :=res + 1
-
-
-
-
root :=root0
-
สำหรับแต่ละขอบ (u, v) และน้ำหนักของมันคือ e ทำ
-
ถ้าคุณเหมือนกับ 2 แล้ว
-
ถ้ายูเนี่ยน (v, w) ไม่ใช่ศูนย์ ดังนั้น
-
edge2 :=edge2 + 1
-
-
มิฉะนั้น
-
res :=res + 1
-
-
-
-
คืนค่า res หาก edge1 เหมือนกับ edge2 และ n - 1
-
มิฉะนั้น ให้คืนค่า -1
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
def แก้(n, e):def find(val):if val !=root[val]:root[val] =find(root[val]) return root[val] def union(val1, val2) :val1, val2 =find(val1), find(val2) if val1 ==val2:return 0 root[val1] =val2 return 1 res =edge1 =edge2 =0 root =list(range(n + 1)) for u , v, w ใน e:if u ==3:if union(v, w):edge1 +=1 edge2 +=1 else:res +=1 root0 =root[:] สำหรับ u, v, w ใน e:if u ==1:if union(v, w):edge1 +=1 else:res +=1 root =root0 for u, v, w ใน e:if u ==2:if union(v, w):edge2 +=1 อื่น:res +=1 return res ถ้า edge1 ==edge2 ==n - 1 อื่น -1print(solve(5, [(0,1,1),(1,2,2),(2, 3,3),(3,4,1),(4,0,2)]))
อินพุต
อินพุต:5, [(0,1,1),(1,2,2),(2,3,3),(3,4,1),(4,0,2)]ผลลัพธ์
-1
