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