[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 119 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
899: 2023/03/29(水)22:23 AAS
1/3重心分解 (one-third centroid decomposition) は、木のアルゴリズムの一種です。木を根付き木として表現したとき、1/3重心分解は、木を3つの部分木に分割することによって木を効率的に処理することができる手法です。
具体的には、まず木の重心を計算し、重心を根とする部分木を1つ、残りの部分木を2つに分割します。このとき、分割された2つの部分木のうち、少なくとも1つの部分木のサイズは元の木のサイズの1/3以下であることが保証されます。
そして、再帰的に各部分木に対して同じ手法を適用することで、木全体を処理します。このとき、各部分木のサイズが1以下になるまで再帰を行います。
1/3重心分解は、木の直径や最大独立集合、最小頂点被覆などの問題を効率的に解くことができることが知られています。また、このアルゴリズムは、計算時間が O(n log n) であり、木のサイズに対して非常に効率的であることが特徴です。
上下前次1-新書関写板覧索設栞歴
あと 103 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.008s