在 Python 中找出图中所有顶点的最小成本总和的程序
假设有一个带 n 个顶点和 m 个边的加权图。边的权重是 2 的幂。任何顶点都可以从图中的任何顶点到达，并且旅行成本将是图中所有边权重的加法。我们必须确定每对顶点之间的最小成本之和。
所以，如果输入像
和顶点数(n)= 6；那么输出将是 2696。
所有距离的总和为 2696。
示例
让我们看看以下实现以更好地理解 -
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 中找出图中所有顶点的最小成本总和的程序 的全部内容， 来源链接： utcz.com/z/363246.html
