縮約を伴ったUnion-Find木は高速に動作することで知られています。以下は蟻本からの抜粋です。 // 木の根を求める int find(int x) { if (par[x] == x) { return x; } else { return par[x] = find(par[x]); } } // xとyの属する集合を併合 void unite(int x…

書庫から久しぶりに取り出したEffective STLをパラパラめくっていて、std::partial_sortのうまい用法を学びました(第31項「ソートの選択肢を知っておこう」)。昇順に整列して初めから20番目の要素までの合計を取りたいときにはstd::sortを使うより、std::par…

先日参加したコンテストで以下のような問題が出題されました1。 シンプルなグラフがある。それぞれの頂点は最大で100個ほどのグループに分けられている。各頂点から各グループの頂点までの最短距離を求めよ。ただし、頂点の最大数は\(10^{5}\)である。 この…