7K12 blog

猫でも分かるアルゴリズム解説

2020-03-10から1日間の記事一覧

重み付きUnionFind木

重み付きUnionFind(ポテンシャル付きUnionFind)は差分制約系 (牛ゲー) の処理が出来る。 Union(x, y, 10); Union(y, z, 20); を実行すると Diff(x, z) の戻り値で30が返ってくる。 この性質を利用するとABC087Dなどがライブラリをコピペするだけで解ける。…