GRL_2_A: Minimum Spanning Tree (続き2)

解説を読む

プリムのアルゴリズムはダイクストラのアルゴリズムと同様に、隣接リストを用い、さらに最小の重みを管理するデータ構造として優先度付きキューを用いることによりO(|E|log|V|)のアルゴリズムとして実装することができます。

知ってた！

ここでは、別のデータ構造を応用したアルゴリズムで最小全域木問題を解きます。

どーん

クラスカルのアルゴリズムね
どれどれ

1. グラフG=(V,E)の辺e1を、重みの昇順（非減少順）に整列する
2. 最小全域木の辺の集合をKとし、それを空に初期化する
3. i=1,2,...,|E|の順番に、|K|が|V|-1になるまで、K∪{ei}が閉路を作らないようなeiをKに追加する

ふーん
閉路を作らないように、か
どうやるんだ？

互いに素な集合(Union-Find)を応用することができます。

あ
今回はプリム＋優先キューだとばっかり思ってたから
ヒントのアイコン見てなかった
高等的整列とUnion-Find使うって書いてあるじゃーん
まあそれはそれで考えてもわからなかったと思うけど

じゃあこれくらいであと自分で書いてみようか
Union-Findってどんなんだっけ
ちっとも覚えられないんだよなー
1000本ノックとか必要

さてDisjoint Setを使ってどうやってやるのかというと
Kに属する頂点をDisjoint Setに追加していくとして
閉路を作らないっていうのは、追加する辺の両端が同じ集合に
含まれないってことか

追加する時は場合分けが必要かな？
両端が同じ集合に属する場合は閉路になるのでスルー
両端とも既存の集合に属する場合はふたつの集合をくっつける
片方だけ既存の集合に属する場合は属さない法の頂点を追加する
両方とも既存の集合に属さない場合は新しく集合を作る
みたいな感じ？

と思って書いてみたら下の3つは全部やることが同じだったという
なお重みの合計を出しているだけで木は作っていない

class DisjointSetElement():
    # 前に書いたのそのまま

class DisjointSet():
    # 前に書いたのそのまま

def read_inputs():
    nv, ne = [int(x) for x in input().split()]

    E = []
    for _ in range(ne):
        s, t, w = [int(x) for x in input().split()]
        E.append((w, s, t))

    return nv, E

def min_sp_tree(nv, E):
    E.sort()
    K = DisjointSet(nv)
    total = 0
    n = 0

    i = iter(E)
    while n < nv - 1:
        w, s, t = next(i)
        if not K.same(s, t):
            K.unite(s, t)
            total += w
            n += 1

    return total

def main():
    nv, E = read_inputs()
    print(min_sp_tree(nv, E))

if __name__ == '__main__':
    main()

プリム＋優先キューのときはCase #18で0.99s 32984KBだったのが
今度は0.67s 24776KB
こっちが速いし小さい

模範解答では追加した辺の数は数えていない
|K|が|V|-1になるまで、って書いてあったのにー

だったらこれでいいわけだな

def min_sp_tree(nv, E):
    E.sort()
    K = DisjointSet(nv)
    total = 0

    for w, s, t in E:
        if not K.same(s, t):
            K.unite(s, t)
            total += w

    return total

ちょっと遅くなって0.76s
意外と違うな