競技プログラミング総合スレ 66 (478ﾚｽ)
上下前次1-新
174: (ﾜｯﾁｮｲ 412d-dXWb) 2023/04/09(日)18:28 ID:fcL4nlHr0(2/3) AAS
>>172
確かに、ヒープにプッシュする前にそのノードがマークされていないことをチェックしています。
ただし、ヒープにプッシュされた後で、そのノードが他の辺を経由してマークされる可能性があります。
そのため、ヒープから辺を取り出す前にもう一度マークされているかどうかをチェックする必要があります。
先程のグラフで考えてみましょう。キューがこの様になったところから解説します。
(1, 3), (1, 1), (1, 3)
ここで、最初に(1, 3)をキューから取り出し、頂点3をマークします。この時点で、キューには以下のような状態が残っています。
(1, 1), (1, 3)
次にキューから取り出す辺は(1, 1)です。この辺は、頂点1と頂点2の間にありますが、頂点1はすでにマークされています。
しかし、この辺をヒープにプッシュした時点では、頂点1はまだマークされていませんでした。
それが、例のコード部分が必要とされる理由です。
あの部分によって、既にマークされた頂点に対応する辺をスキップし、正しい最小全域木を構築することができます。
上下前次1-新書関写板覧索設栞歴
あと 304 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.007s