AtCoder Beginner Contest 270 F問題 Transportation

問題

AtCoder 国は $N$ 個の島からなる島国である. 最初, どの島にも空港, 港はなく, どの2つの島の間にも道路はない.

次のことをそれぞれ好きなだけ行うことができる.

以下の行動を繰り返すことによって島 $U$ から島 $V$ へ移動できるとき, 島 $U$ から島 $V$ へ移動可能であるという.

任意の2つの島の間を移動可能にするために必要な最小費用を求めよ.

次のような (重み付き) 無向グラフ $G=(V,E)$ を考える. ただし, $A,P$ は形式的につける頂点とする *1.

$V:=\{1,2, \dots, N, A, P\}$
$E:=\{A_j B_j \mid j=1,2, \dots, M\} \cup \{i A \mid i=1,2, \dots, N \} \cup \{i P \mid i=1,2, \dots, N\}$

このようにすることで, それぞれ以下が成り立つ.

よって, この問題は $G$ において頂点 $1,2, \dots, N$ を連結にするために必要な残す辺の重みの総和の最小値を求める問題に帰着された. ここで, 頂点 $A,P$ に対する連結性については言及されていないことから, $2^2=4$ 通りの場合分けをすることにする.

すると, 各問題は次のようにして帰着される.

$A,P$ ともに頂点 $1,2, \dots, N$ と連結しない場合 $\cdots$ 無向グラフ $G-\{A,P\}$ における最小全域木問題.
$A$ は頂点 $1,2, \dots, N$ と連結しないが, 頂点 $P$ 連結する場合 $\cdots$ 無向グラフ $G-\{A\}$ における最小全域木問題.
$P$ は頂点 $1,2, \dots, N$ と連結しないが, 頂点 $A$ 連結する場合 $\cdots$ 無向グラフ $G-\{A\}$ における最小全域木問題.
$A,P$ ともに頂点 $1,2, \dots, N$ と連結する場合 $\cdots$ 無向グラフ $G$ における最小全域木問題.