競技プログラミング総合スレ 66
- 171 :デフォルトの名無しさん (ワッチョイ 412d-dXWb):2023/04/09(日) 18:19:09.47 ID:fcL4nlHr0.net
- この部分は、既にマークされた頂点に対応する辺をスキップするために必要です。
確かに、キューには基本的にmarkedの値がFalseのノードしか入らないように見えますが、
実際には同じノードに対して複数の辺がキューに入ることがあります。
例えば、次のようなグラフを考えてみましょう。
1 -- 2
| /
| /
3
各辺の重みはすべて1とします。最初に頂点1を選び、marked[1]=Trueとします。
次に、頂点1に隣接する辺をキューに追加します。
この時点でキューの状態は以下のようになります。
(1, 2), (1, 3)
次に、キューから最小の重みの辺を取り出し、それに接続されている頂点2をマークします。
頂点2に隣接する辺をキューに追加します。
この時点でキューの状態は以下のようになります。
(1, 3), (1, 1), (1, 3)
ここで、次にキューから取り出す辺が(1, 1)であることに注意してください。
ただし、頂点1はすでにマークされているため、この辺を使ってしまうと、最小全域木の条件を満たさなくなります。
これが、以下のコード部分が必要とされる理由です。
if marked[i]:
continue
この部分によって、既にマークされた頂点に対応する辺をスキップし、
正しい最小全域木を構築することができます。
109 KB
新着レスの表示
掲示板に戻る
全部
前100
次100
最新50
read.cgi ver.24052200