โปรแกรมนับจำนวนการสืบค้นที่เป็นจริงในกราฟที่มีเส้นทางแบบถ่วงน้ำหนักใน C++

สมมติว่าเรามีรายการขอบสำหรับกราฟที่ไม่มีทิศทาง โดยแต่ละขอบมีฟิลด์ [u, v, w] u และ v คือจุดยอดต้นทางและปลายทาง และ w คือน้ำหนัก และยังมีรายการแบบสอบถามในรูปแบบเดียวกัน [u, v, w] นั่นแสดงถึงคำถามว่า มีเส้นทางระหว่าง u และ v หรือไม่ โดยที่ขอบแต่ละด้านในเส้นทางมีน้ำหนักมากที่สุด w ดังนั้นจงหาจำนวนคำถามที่เป็นจริง

ดังนั้น หากอินพุตเป็นเหมือนขอบ =[[0, 1, 6],[1, 2, 7],[2, 3, 8],[0, 3, 5]] การสืบค้นข้อมูล =[[0, 2, 14],[1, 0, 3]]

จากนั้นผลลัพธ์จะเป็น 1 เนื่องจากเราสามารถไปจากโหนด 0 ถึง 2 โดยทำตามเส้นทางนี้ [0, 1, 2] ด้วยน้ำหนัก 13 แต่ไม่มีเส้นทางจาก 1 ถึง 0 ที่มีน้ำหนักขอบ 3

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

• กำหนดฟังก์ชัน get_parent() ซึ่งจะใช้ x ซึ่งเป็นพาร์อาร์เรย์
• ถ้า par[x] ไม่ใช่ x แล้ว
  • par[x] :=get_parent(par[x], par)
• ผลตอบแทนพาร์[x]
• จากวิธีหลัก ให้ทำดังนี้ -
• กำหนดหนึ่งอาร์เรย์ 2 มิติ gr
• n :=0
• สำหรับแต่ละขอบ t ในขอบ −
  • n :=สูงสุด n, t[0] และ t[1]
  • แทรกแถว [t[2], 0, t[0], t[1]] ลงใน gr
• สำหรับแต่ละเคียวรี t ในเคียวรี −
  • แทรกแถว [t[2], 1, t[0], t[1]] ลงใน gr
• จัดเรียง gr
• กำหนดพาร์อาร์เรย์ขนาด n + 1 และเติมด้วย -1
• สำหรับการเริ่มต้น i :=0 เมื่อฉัน <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ −
  • พาร์[i] :=ฉัน
• sz :=ขนาดของข้อความค้นหา
• ตอบ :=0
• สำหรับแต่ละแถว t ใน gr
  • a :=t[2], b :=t[3], tp :=t[1], d :=t[0]
  • px :=get_parent(a, par)
  • py :=get_parent(b, par)
  • ถ้า tp เหมือนกับ 0 แล้ว −
    • ถ้า px ไม่เท่ากับ py แล้ว −
      • พาร์[py] :=px
  • มิฉะนั้น
    • ถ้า px เหมือนกับ py แล้ว −
      • (เพิ่ม ans 1)
    • (ลด sz ลง 1)
    • ถ้า sz เหมือนกับ 0 แล้ว −
      • ออกมาจากวงจร
• คืนสินค้า

ตัวอย่าง (C++)

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

#include ใช้เนมสเปซ std;int get_parent(int x, vector&par) { if (par[x] !=x) { par[x] =get_parent(par[ x], พาร์); } return par[x];}int แก้ไข (vector>&edge, vector>&แบบสอบถาม) { vector> gr; int n =0; สำหรับ (อัตโนมัติ เสื้อ :ขอบ) { n =สูงสุด (n, สูงสุด (t[0], t[1])); gr.push_back({t[2], 0, t[0], t[1]}); } สำหรับ (อัตโนมัติ t :คำสั่ง) { gr.push_back({t[2], 1, t[0], t[1]}); } sort(gr.begin(), gr.end()); vector พาร์ (n + 1, -1); สำหรับ (int i =0; i <=n; i++) { par [i] =i; } int sz =query.size(); int ans =0; สำหรับ (อัตโนมัติ t :gr) { int a =t[2]; int b =เสื้อ[3]; int tp =t[1]; int d =t[0]; int px =get_parent(a, ตราไว้หุ้นละ); int py =get_parent(b, พาร์); if (tp ==0) { if (px !=py) { par [py] =px; } } อื่น { ถ้า (px ==py) { ans ++; } sz--; ถ้า (sz ==0) { แตก; } } } return ans;}int main(){ vector> edge ={{0, 1, 6},{1, 2, 7},{2, 3, 8},{0, 3 , 5}}; vector> แบบสอบถาม ={{0, 2, 14},{1, 0, 3}}; ศาล <<แก้ (ขอบ แบบสอบถาม);}

อินพุต

ผลลัพธ์

1