Python程式：查詢圖中所有頂點之間最小成本的總和

假設有一個帶權圖，包含n個頂點和m條邊。邊的權重為2的冪。圖中任何頂點都可以從任何其他頂點到達，並且旅行的成本將是圖中所有邊權重的總和。我們需要確定每對頂點之間最小成本的總和。

因此，如果輸入如下所示：

並且頂點數 (n) = 6；則輸出將為 2696。

所有距離的總和為 2696。

為了解決這個問題，我們將遵循以下步驟：

  • 定義一個函式 par_finder()。它將接收 i 和 par 作為引數。
    • 如果 par[i] 等於 -1，則
      • 返回 i
    • res := par_finder(par[i], par)
    • par[i] := res
    • 返回 res
  • 定義一個函式 helper()。它將接收 i、par、w、G 和 n 作為引數。
    • child := 1
    • 對於 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)
      • 返回 child
  • G := 一個新的列表，包含 n + 1 個其他列表
  • edges := 一個新的列表
  • 對於 roads 中的每個專案，執行以下操作：
    • u := item[0]
    • v := item[1]
    • w := item[2]
    • 在 edges 的末尾插入 (u-1, v-1, w)
  • 根據邊權重對列表 edges 進行排序
  • par := 一個大小為 n + 1 的新列表，初始化為 -1
  • r_edge := 一個新的列表
  • 對於 edges 中的每個 i，執行以下操作：
    • 如果 par_finder(i[0], par) 等於 par_finder(i[1], par)，則
      • 跳過本次迭代
    • 否則，
      • 在 r_edge 的末尾插入 i
      • 在 G[i[0]] 的末尾插入對 (i[1],i[2])
      • 在 G[i[1]] 的末尾插入對 (i[0],i[2])
      • par[par_finder(i[0], par)] := par_finder(i[1], par)
  • ans := 0
  • helper(0, -1, 0, G, n)
  • 返回 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

更新於： 2021年10月6日

380 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告