競技プログラミング総合スレ 66 (478ﾚｽ)
上
下
前
次
1-
新
190
:
(ﾜｯﾁｮｲ 412d-dXWb)
2023/04/10(月)16:12
ID:GqegRxcS0(1/4)
AA×
[240|
320
|
480
|
600
|
100%
|
JPG
|
べ
|
ﾚｽ栞
|
ﾚｽ消
]
190: (ﾜｯﾁｮｲ 412d-dXWb) [sage] 2023/04/10(月) 16:12:48.08 ID:GqegRxcS0 確かに、その解法ではトポロジカルソートを明示的に実行していないように見えますが、 実際にはトポロジカルソートの考え方が含まれています。DAGの最長パスを求める際、 トポロジカルソートの概念が重要なのは、頂点の順序付けによって依存関係を解決することができるからです。 その解法で、indegree（入次数）が0の頂点からDPを用いて最長パスを求めています。これは、各頂点について、 その頂点に入ってくる辺がなくなる（依存関係が解決される）順序で処理を行っていることを意味します。 この順序付けがトポロジカルソートの結果と同じです。 indegreeが0になる頂点から処理を行い、その後、処理された頂点から出る辺を削除することで、 indegreeが0になる頂点が次々と現れます。この手順は、トポロジカルソートを実行する手順と同じです。 したがって、トポロジカルソートを明示的に行わなくても、その考え方が解法に含まれているため、 問題を解決することができます。トポロジカルソートの概念は、DAGの最長パス問題を解く際の重要な考え方であることがわかります。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/190
確かにその解法ではトポロジカルソートを明示的に実行していないように見えますが 実際にはトポロジカルソートの考え方が含まれていますの最長パスを求める際 トポロジカルソートの概念が重要なのは頂点の順序付けによって依存関係を解決することができるからです その解法で入次数がの頂点からを用いて最長パスを求めていますこれは各頂点について その頂点に入ってくる辺がなくなる依存関係が解決される順序で処理を行っていることを意味します この順序付けがトポロジカルソートの結果と同じです がになる頂点から処理を行いその後処理された頂点から出る辺を削除することで がになる頂点が次と現れますこの手順はトポロジカルソートを実行する手順と同じです したがってトポロジカルソートを明示的に行わなくてもその考え方が解法に含まれているため 問題を解決することができますトポロジカルソートの概念はの最長パス問題を解く際の重要な考え方であることがわかります
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 288 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
ぬこの手
ぬこTOP
0.031s