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個という特殊データなので
まともな答えが出てるのはふたつだけ
ちゃんと動いてるかは少しこころもとない