普通に難しかった。
E - Weights on Vertices and Edges
問題
N頂点M辺の無向グラフが与えられる。頂点と辺には重みがついている。
このグラフから辺を何本か取り去って、残っている辺がすべて以下の条件を満たすようにしたい:
- 辺の重みをYとすると、その辺を含む連結成分の頂点の重みの合計はY以上である。
条件を満たすために取り去るべき辺の本数の最小値を求めよ。
解法
辺eについて、e以下の重みの辺を繋げたときに、繋がる頂点の重みの合計がeの重み以上となる場合、eを使える辺と呼ぶことにする。
ある辺eに着目したとき、その辺を残しても良いのは以下が成り立つ場合である:
- ある使える辺fであって、f以下の重みの辺を繋げた時にeにつながるものが存在する
- e自体が使える辺である場合ももちろんこの条件は満たされる
このような辺を列挙したい。単純に使える辺全てに対してDFSをするとTLEしてしまう。使える辺を重みの大きい順に見ていき、すでに残せることがわかっている辺はスキップすると、合計O(N + M)時間でできる。全体の計算量はO(N + M log M)である。
登場する典型
- 辺ごとに独立に考える
- DFSをうまく行い、計算量の合計をO(N + M)にする
実装上の注意点
特になし。難しいので気をつける
提出: #4111631 (Rust)
fn solve() { let out = std::io::stdout(); let mut out = BufWriter::new(out.lock()); macro_rules! puts { ($($format:tt)*) => (write!(out,$($format)*).unwrap()); } macro_rules! debug { ($($format:tt)*) => ();//(eprintln!($($format)*)); } input! { n: usize, m: usize, x: [i64; n], aby: [(usize1, usize1, i64); m], } let mut aby = aby; aby.sort_by_key(|&(_, _, y)| y); let mut uf = UnionFind::new(n); let mut wei = x.clone(); let mut usable = vec![false; m]; for (i, &(a, b, y)) in aby.iter().enumerate() { if !uf.is_same_set(a, b) { let a = uf.root(a); let b = uf.root(b); uf.unite(a, b); let nr = uf.root(a); let oldwei = wei[a + b - nr]; wei[a + b - nr] = -1; wei[nr] += oldwei; } let root = uf.root(a); debug!("(a, b, y) = {} {} {}", a, b, y); if wei[root] >= y { debug!("Edge {} (wei = {}) is usable", i, y); usable[i] = true; } } let mut g = vec![vec![]; n]; for (i, &(a, b, y)) in aby.iter().enumerate() { g[a].push((b, y, i)); g[b].push((a, y, i)); } let mut covered = vec![false; m]; for i in (0..m).rev() { let (a, _b, y) = aby[i]; if usable[i] { dfs(a, &g, y, &mut covered); } } let mut unusable = 0; for i in 0..m { if !covered[i] { unusable += 1; } } puts!("{}\n", unusable); }
まとめ
最初Kruskal法の構成過程を見て、最後に条件を満たした森に適当に辺を加えればOKだと思ったけど、全然ダメだった(は?)
- 反例: [1]-3-[1]-10-[100]
