โปรแกรมหลามเพื่อค้นหาดีเทอร์มีแนนต์ของเมทริกซ์พิเศษที่กำหนด

สมมุติว่าเรามีต้นไม้ที่มีจุดยอด n จุด โดยแต่ละจุดมีจุดยอดตั้งแต่ 1 ถึง n รากของต้นไม้มีป้ายกำกับ 1 และจุดยอดแต่ละจุดมีน้ำหนัก wi ตอนนี้เมทริกซ์ nxn A ก่อตัวขึ้นโดยที่ A(x,y) =Wf(x, y) โดยที่ f(x, y) เป็นบรรพบุรุษร่วมกันน้อยที่สุดของจุดยอด x และ y เราต้องหาดีเทอร์มีแนนต์ของเมทริกซ์ A ค่าขอบของเมทริกซ์ น้ำหนัก และจำนวนจุดยอดทั้งหมดเป็นข้อมูลป้อนเข้า

ดังนั้น ถ้าอินพุตเหมือนกับ input_array =[[1, 2], [1, 3], [1, 4], [1, 5]], น้ำหนัก =[1, 2, 3, 4, 5], จุดยอด =5 จากนั้นผลลัพธ์จะเป็น 24

เมทริกซ์ A ถูกกำหนดเป็น =

ดีเทอร์มีแนนต์ของเมทริกซ์นี้คือ 24

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

• w :=รายการว่าง
• สำหรับฉันในช่วง 0 ถึงจุดยอด ทำ
  • เพิ่มน้ำหนัก[i] และรายการใหม่ให้กับ w
• สำหรับแต่ละ i รายการใน enumerate(input_array), do
  • p :=item[0]
  • q :=item[1]
  • ใส่ q - 1 ต่อท้าย w[p - 1, 1]
  • แทรก p - 1 ที่ส่วนท้ายของ w[q - 1, 1]
• เดต :=1
• stack :=สแต็คที่มีทูเพิล (0, 0)
• ในขณะที่สแต็กไม่ว่างเปล่า ให้ทำ
  • i, weights :=ลบองค์ประกอบด้านบนออกจากสแต็ก
  • det :=(det * (w[i, 0] - weights)) mod (10^9 + 7)
  • สำหรับ t ใน w[i][1] ทำ
    • เพิ่มทูเพิลที่มี (t,w[i,0]) ลงในสแต็ก
    • สำหรับแต่ละ t ใน w[i][1] ทำ
      • ลบ i จาก w[t,1]
• คืนสินค้า

ตัวอย่าง

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

def solve(input_array, weights, vertices):
   w = [[weights[i],[]] for i in range(vertices)]
   for i, item in enumerate(input_array):
      p,q = item[0], item[1]
      w[p - 1][1].append(q - 1)
      w[q - 1][1].append(p - 1)
   det = 1
   stack = [(0,0)]
   while stack:
      i, weights = stack.pop()
      det = (det * (w[i][0] - weights)) % (10**9 + 7)
      stack += [(t,w[i][0]) for t in w[i][1]]
      for t in w[i][1]:
         w[t][1].remove(i)
   return det
print(solve([[1, 2], [1, 3], [1, 4], [1, 5]], [1, 2, 3, 4, 5], 5))

อินพุต

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

ผลลัพธ์

24