library-checker-problems
library-checker-problems copied to clipboard
yosupo06
[問題案] Incremental Minimum Spanning Forest
問題ID: incremental_msf 問題名: Incremental Minimum Spanning Forest
想定アルゴリズム: link-cut tree で maximum を管理する。 参考資料: https://atcoder.jp/contests/joisc2022/tasks/joisc2022_l
https://atcoder.jp/contests/pakencamp-2021-day3/tasks/pakencamp_2021_day3_g https://twitter.com/SSRS_cp/status/1508735586718613507
問題概要
$N$ 頂点のグラフの $M$ 個の重み付き無向辺が順に与えられる。番号が $i$ 未満の辺のみを採用した場合の最小全域森を $F_i$ とする。各辺 $k$ について、辺 $k$ が $F_i$ に含まれるような最大の $i$ 、あるいはそのような $i$ が存在しなければ $k$ を求めよ。
入力
N M
u[0] v[0] w[0]
u[1] v[1] w[1]
:
u[M-1] v[M-1] w[M-1]
出力
空白区切りで $M$ 個
制約
1 <= N <= 200 000 1 <= M <= 200 000 w は 1..M の順列
これと Vertex Add Subtree Sum を合わせると Dynamic Graph Vertex Add Component Sum のオフライン解法になるはず
Static Range Components Number とかでしょうか 問題設定がわりと複雑なんで、タイトルで内容をぜんぶ表すのは難しいですね
- 元の問題案を変えた理由があれば教えてください（個人的には元の方が学びがあって好きかも）
- 今の形式：「辺を足すたびに、消す辺があればそれを出力、なければ -1 を出力」とかでもいいかも
-
Incremental MST （を計算して、辺が捨てられるタイミングをとる）が使えるパターンがいくつかあると思っていて、そういう場合に前の問題設定だと複雑すぎてあまり嬉しくなさそうだと思って変えました。
-
本質に差がなければ（なさそう）、辺を足すたびに消す辺を出力のほうが綺麗そうです。