kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

GRL_2_A: Minimum Spanning Tree

最小全域木を求めるというところはALDS1_12_Aと同じ
隣接行列では大きくなりすぎるからか、
入力形式が隣接リスト形式になっているくらい

ALDS1_12_Aでは頂点が100個までだったのに対し
こちらでは10000までというのが違い

これは予告どおりの展開でALDS1_12_Aにこう書いてあったとおり

プリムのアルゴリズムは、二分ヒープ(優先度付きキュー)を使って頂点を決定するようにすれば、高速化を行うことができます。

でもまずはプリムのアルゴリズムを思い出しがてらALDS1_12_Aのまま動かしてみる

from sys import maxsize

WHITE = 0
GRAY = 1
BLACK = 2

class Node():
    def __init__(self, key):
        self.key = key
        self.color = WHITE
        self.d = maxsize
        self.p = -1
        self.adj = []

def read_inputs():
    nv, ne = [int(x) for x in input().split()]
    G = [Node(k) for k in range(nv)]
    for _ in range(ne):
        s, t, w = [int(x) for x in input().split()]
        G[s].adj.append((G[t], w))
        G[t].adj.append((G[s], w))
    return G

def weight_between(G, u, v):
    for a, w in u.adj:
        if a == v:
            return w

def min_sp_tree(G):

    G[0].d = 0

    while True:
        minv = maxsize
        u = None

        for v in G:
            if minv > v.d and v.color != BLACK:
                u = v
                minv = v.d

        if u is None:
            break

        u.color = BLACK
        for v in G:
            if v.color == BLACK:
                continue
            for a, w in u.adj:
                if a != v:
                    continue
                if v.d > w:
                    v.d = w
                    v.p = u
                    v.color = GRAY

    return sum([weight_between(G, v.p, v) for v in G if v.p != -1])

def main():
    G = read_inputs()
    print(min_sp_tree(G))

if __name__ == '__main__':
    main()

Case #4でAC
Case #4でいきなり10000頂点なのでこれはしかたないとして
Case #3は頂点1個という特殊データなので
まともな答えが出てるのはふたつだけ
ちゃんと動いてるかは少しこころもとない