競技プログラミング総合スレ 66 (478ﾚｽ)
上
下
前
次
1-
新
171
(2)
:
(ﾜｯﾁｮｲ 412d-dXWb)
2023/04/09(日)18:19
ID:fcL4nlHr0(1/3)
AA×
[240|
320
|
480
|
600
|
100%
|
JPG
|
べ
|
ﾚｽ栞
|
ﾚｽ消
]
171: (ﾜｯﾁｮｲ 412d-dXWb) [sage] 2023/04/09(日) 18:19:09.47 ID:fcL4nlHr0 この部分は、既にマークされた頂点に対応する辺をスキップするために必要です。 確かに、キューには基本的に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 この部分によって、既にマークされた頂点に対応する辺をスキップし、 正しい最小全域木を構築することができます。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/171
この部分は既にマークされた頂点に対応する辺をスキップするために必要です 確かにキューには基本的にの値がのノードしか入らないように見えますが 実際には同じノードに対して複数の辺がキューに入ることがあります 例えば次のようなグラフを考えてみましょう 各辺の重みはすべてとします最初に頂点を選びとします 次に頂点に隣接する辺をキューに追加します この時点でキューの状態は以下のようになります 次にキューから最小の重みの辺を取り出しそれに接続されている頂点をマークします 頂点に隣接する辺をキューに追加します この時点でキューの状態は以下のようになります ここで次にキューから取り出す辺が であることに注意してください ただし頂点はすでにマークされているためこの辺を使ってしまうと最小全域木の条件を満たさなくなります これが以下のコード部分が必要とされる理由です この部分によって既にマークされた頂点に対応する辺をスキップし 正しい最小全域木を構築することができます
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 307 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
ぬこの手
ぬこTOP
0.035s
