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 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告