HTML CSS JAVASCRIPT JQUERY AI PHP SQL EXCEL LINUX C# C++ C PYTHON JAVA 教程库 参考手册 技术文章 测验 练习 HOWTO FAQ

用 Python 编写程序，找出图中所有顶点的最小成本之和

pythonserver side programmingprogramming更新于 2025/12/2 18:20:17

假设有一个加权图，其中有 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]
    • 在 edge 末尾插入 (u-1, v-1, w)
  • 按边权重对列表 edge 进行排序
  • par := 一个大小为 n + 1 的新列表，用 -1 初始化
  • r_edge := 一个新列表
  • 对于 edge 中的每个 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

相关文章

有用资源

打印 下一节:用 Python 编写一个程序，计算从删除子字符串中获得的最高分数 ❯❮ 上一节:用 Python 编写程序，找出投递所有信件的最短路径