Pythonのすべての頂点の中でグラフ内の最小コストの合計を見つけるプログラム

n個の頂点とm個のエッジを持つ重み付きグラフがあるとします。エッジの重みは2の累乗です。グラフ内の任意の頂点から任意の頂点に到達でき、移動コストはグラフ内のすべてのエッジの重みを加算したものになります。頂点の各ペア間の最小コストの合計を決定する必要があります。

したがって、入力が次のような場合

頂点の数（n）=6;その場合、出力は2696になります。

すべての距離の合計は2696です。

これを解決するには、次の手順に従います-

• 関数par_finder（）を定義します。これにはi、par
  が必要です
  • par [i]が-1と同じ場合、
    • 私を返す
  • res：=par_finder（par [i]、par）
  • par [i]：=res
  • return res
• 関数helper（）を定義します。これには、i、par、w、G、n
  が必要です。
  • 子：=1
  • G [i]の各アイテムについて、
    • item [0]がparと同じ場合、
      • 次の反復に進む
    • それ以外の場合、
      • 子：=子+ヘルパー（item [0]、i、item [1]、G、n）
    • parが-1と同じでない場合、
      • ans：=ans + child *（n --child）*（1 * 2 ^ w）
    • 子を返す
• G：=n+1個の他のリストを含む新しいリスト
• edges：=新しいリスト
• 道路の各アイテムについて、
  • u：=item [0]
  • v：=item [1]
  • w：=item [2]
  • エッジの端に（u-1、v-1、w）を挿入します
• リストのエッジをエッジの重みで並べ替えます
• par：=-1で初期化されたサイズn+1の新しいリスト
• r_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）
• 回答を返す

例

理解を深めるために、次の実装を見てみましょう-

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