po

ねいしょん

C: 高橋君と国家 - AtCoder Regular Contest 029 | AtCoder

この回は解説スライドがとても丁寧です!(一般人にはありがたい。)

問題概要

N頂点のグラフがある。

辺の候補がM本用意されており、それぞれの辺を採用するのにコストがrだけかかる。

また、各頂点に対してコストcでその頂点を“いい頂点”にできる。

“いい頂点”と連結になっている頂点も“いい頂点”になる。

N個の頂点全てを“いい頂点”にするための最小コストを求めよ。

解き方

“いい頂点”にする操作がむずいので、$N+1$個目の仮想的な頂点を作ります。以降これを$v$と呼びます。$v$から頂点$i(0\leq i\leq N)$へコスト$c_i$の辺を考えると、頂点$i$を“ いい頂点”にする操作は$i$と$v$を結ぶ辺を採用する操作と考えることができます。結局、次の問題を解けばいいことになりました。

N+1個の頂点とM+N本の辺の候補があるので、辺を適当に採用してグラフが連結になるようにしたい。ただし、辺を採用することによるコストの総和を最小にしなければならない。

これはよく知られている問題で、最小全域木(MST)を求める問題です。最小全域木を求める方法として主にクラスカル法とプリム法の2つが知られています。

クラスカル
  • コストの小さい辺から見ていく。
  • もし、その辺を採用して閉路ができるなら採用しない。できないなら採用する。
  • 辺をぜんぶ見たらおわり。

閉路検出パートにはUnionFindを使うと高速にできます。

プリム法
  • 部分的にMSTが求まっているとする。
  • MSTに含まれている頂点から、含まれない頂点に張られている辺のうち、コストが最小のものを採用してMSTを広げる。
  • 全ての頂点がMSTに含まれたらおわり。

初めに、どれか適当に頂点を1個選べばMSTとなるのでそこから始めます。頂点がMSTに含まれているかどうかは配列で管理できます。使える辺の中でコストが最小のものを選ぶ操作は、優先度付きキューを使うと高速にできます。

解答例

ARC 029-C 高橋君と国家


ARC 029-C 高橋君と国家

おわりに

新しく頂点を作るのがすごい。

参考

最小全域木(クラスカル法とUnionFind) - アルゴリズム講習会

プリム法(最小全域木問題)