プリム法

[tipstar0125]

https://algo-logic.info/prim-mst/

[tipstar0125]

• 適当に1点を木に含め、確定する
• 確定した点から、出ている全ての辺を優先キューにいれて、最小辺から選んでいく。ただし、既に確定されている点との辺の場合はcontinue
• ダイクストラっぽくやる

[tipstar0125]

input! {
    N: usize,
    M: usize,
    ABC: [(usize, usize, usize); M]
}

let mut G = vec![vec![]; N];
for &(a, b, c) in &ABC {
    G[a - 1].push((b - 1, c));
    G[b - 1].push((a - 1, c));
}

let mut used = vec![false; N];
let mut Q = BinaryHeap::new();
let mut ans = 0_usize;
used[0] = true;
for &(v, c) in &G[0] {
    Q.push((Reverse(c), v));
}
while let Some((Reverse(c), u)) = Q.pop() {
    if used[u] {
        continue;
    }
    used[u] = true;
    ans += c;
    for &(v, nc) in &G[u] {
        if !used[v] {
            Q.push((Reverse(nc), v));
        }
    }
}
println!("{}", ans);

[tipstar0125]

ジャッジ：https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_bo 解答：https://atcoder.jp/contests/tessoku-book/submissions/47607753

[tipstar0125]

計算量(V: 頂点、E: 辺)

• クラスカル: O(ElogE)
• プリム: O(E+VlogV)、特に辺の数が、頂点に比べて十分大きい場合はO(E)