最小全域木

重み付き無向グラフが与えられた時それらの全ての頂点を結ぶような木の最小のコストを求める問題です。
主なアルゴリズムには、プリム法とクラスカル法がありますが、計算量は共にO(ElogV)で等しいです。色々調べたところ、基本はクラスカル法を使うのがよさげです。

クラスカル法

クラスカル法は以下のように貪欲に最小全域木を求めます。
まだ用いていない最小のコストの辺をそれを付け加えることで、閉路が生じない限り、付け加えていく。
これで正しく最小全域木が求められる証明は蟻本を読みましょう。
閉路が生じる＝その辺で結ばれる二つの頂点がすでに連結であることを確かめるのにUnionFindを用いればO(Elogv)で求めることができます。

V, E = map(int, input().split())
edges = []
for i in range(E):
    s, t, w = map(int, input().split())
    edges.append((w, s-1, t-1))
edges.sort()

def kruskal(n, edges):#edges: wでソート済み
    U = UnionFind(n)
    res = 0
    for e in edges:
        w, s, t = e
        if not U.same(s, t):
            res+=w
            U.unite(s, t)
    return res
print(kruskal(V, edges))

verify用問題