Codeforces Round #529 (Div. 3) F. Make It Connected
まあ、基本ですね。
Problem - F - Codeforces
問題
長さnの数列aが与えられる。このaを用いて、n頂点の完全グラフであって、iとjを結ぶ辺のコストがa[i]+a[j]であるものを作る。
この完全グラフにm本の辺(x_i,y_i,w_i)を加える(w_iはコスト)。加えた後のグラフの最小全域木のコストを求めよ。
1 <= n <= 2 * 10^5
0 <= m <= 2 * 10^5
1 <= a_i <= 10^12
1 <= w_i <= 10^12
解法
最小全域木はKruskal法、Prim法(、時々Boruvka法)を適用すべしの原則に基づいて何を適用するかを考えると、今回はPrim法がぴったりであることがわかる。
a[v]が最小となるvを選び、vからなる1点集合{v}にa[i]+a[v]や加えられた辺によるコストの小さい順に頂点を追加していけばよい。
実装上の注意点
- 単に頂点0に点を追加していく方針でもおそらくできるが、a[v]が最小の点vから始める方が楽。
- コストが64bit整数の範囲内に収まるか確認する。今回は最大10^12 * 2*10^5 = 2*10^17 < 2^60なのでOK。
提出: https://codeforces.com/contest/1095/submission/47608560 (Rust)
fn solve() { let out = std::io::stdout(); let mut out = BufWriter::new(out.lock()); macro_rules! puts { ($($format:tt)*) => (write!(out,$($format)*).unwrap()); } input! { n: usize, m: usize, a: [i64; n], xyw: [(usize1, usize1, i64); m], } let mut g = vec![Vec::new(); n]; for (x, y, w) in xyw { g[x].push((y, w)); g[y].push((x, w)); } let mut amin = (1 << 50, n); for i in 0 .. n { amin = min(amin, (a[i], i)); } // Prim let mut tot = 0; let (added, init) = amin; let mut used = vec![false; n]; used[init] = true; let mut que = BinaryHeap::new(); for i in 0 .. n { if init != i { que.push(Reverse((a[i] + added, i))); } } for &(w, cost) in g[init].iter() { que.push(Reverse((cost, w))); } while let Some(Reverse((cost, v))) = que.pop() { if used[v] { continue; } tot += cost; used[v] = true; for &(w, cost) in g[v].iter() { que.push(Reverse((cost, w))); } } puts!("{}\n", tot) }
まとめ
Prim法書いたことなかったので練習になってよかった。