โปรแกรมหาผลรวมค่าใช้จ่ายขั้นต่ำในกราฟระหว่างทุกคู่จุดยอดใน Python

สมมติว่ามีกราฟมีน้ำหนัก n จุดยอด และ m เส้นขอบ น้ำหนักของเส้นขอบเป็นกำลังของ 2 จุดยอดใดๆ สามารถเข้าถึงจากจุดยอดอื่นได้ และค่าใช้จ่ายในการเดินทางคือผลรวมของน้ำหนักเส้นขอบทั้งหมดในเส้นทาง เราต้องหาผลรวมของค่าใช้จ่ายขั้นต่ำระหว่างแต่ละคู่ของจุดยอด

เช่น ถ้าอินพุตเป็นดังภาพ และจำนวนจุดยอด (n) = 6 ผลลัพธ์จะเป็น 2696 ผลรวมของระยะทางทั้งหมดคือ 2696

วิธีแก้ปัญหา

• กำหนดฟังก์ชัน par_finder() รับ i, par:
  • ถ้า par[i] เท่ากับ -1 return i
  • res := par_finder(par[i], par)
  • par[i] := res
  • return res
• กำหนดฟังก์ชัน helper() รับ i, par, w, G, n:
  • child := 1
  • สำหรับแต่ละ item ใน G[i]:
    • ถ้า item[0] เท่ากับ par ข้ามรอบนี้
    • มิฉะนั้น child := child + helper(item[0], i, item[1], G, n)
  • ถ้า par ไม่เท่ากับ -1: ans := ans + child * (n - child) * (1 * 2^w)
  • return child
• G := รายการใหม่ที่มี n + 1 รายการย่อย
• edges := รายการใหม่
• สำหรับแต่ละ item ใน roads:
  • u := item[0], v := item[1], w := item[2]
  • แทรก (u-1, v-1, w) ลงท้าย edges
• เรียง edges ตามน้ำหนักเส้นขอบ
• par := รายการใหม่ขนาด n + 1 เริ่มต้นด้วย -1
• r_edge := รายการใหม่
• สำหรับแต่ละ i ใน edges:
  • ถ้า par_finder(i[0], par) เท่ากับ par_finder(i[1], par) ข้ามรอบนี้
  • มิฉะนั้น:
    • แทรก i ลงท้าย r_edge
    • แทรกคู่ (i[1],i[2]) ลงท้าย G[i[0]]
    • แทรกคู่ (i[0],i[2]) ลงท้าย G[i[1]]
    • par[par_finder(i[0], par)] := par_finder(i[1], par)
• ans := 0
• helper(0, -1, 0, G, n)
• return ans

ตัวอย่าง

def par_finder(i, par):
    if par[i] == -1:
        return i
    res = par_finder(par[i], par)
    par[i] = res
    return res

def helper(i, par, w, G, n):
    global ans
    child = 1
    for item in G[i]:
        if item[0] == par:
            continue
        else:
            child += helper(item[0], i, item[1], G, n)
    if par != -1:
        ans += child * (n - child) * (1 << w)
    return child

def solve(n, roads):
    global ans
    G = [[] for i in range(n + 1)]
    edges = []
    for item in roads:
        u, v, w = map(int, item)
        edges.append((u-1, v-1, w))
    edges = sorted(edges, key=lambda item: item[2])
    par = [-1 for i in range(n + 1)]
    r_edge = []
    for i in edges:
        if par_finder(i[0], par) == par_finder(i[1], par):
            continue
        else:
            r_edge.append(i)
            G[i[0]].append((i[1], i[2]))
            G[i[1]].append((i[0], i[2]))
            par[par_finder(i[0], par)] = par_finder(i[1], par)
    ans = 0
    helper(0, -1, 0, G, n)
    return ans

print(solve(6, [(1,4,8), (2,4,4), (3,4,4), (3,4,2), (5,3,8), (6,3,2)]))

อินพุต

6, [(1,4,8), (2,4,4), (3,4,4), (3,4,2), (5,3,8), (6,3,2)]

เอาต์พุต

2696