この問題は以下のようにグラフの問題に言い換えることができます。

\(N\) 個のタワーと \(M\) 個の環状交差点に対応する頂点が各 \(1\) つずつあるような \(N + M\) 頂点のグラフを作る。
全ての \(2\) 頂点間に辺を張る。辺の重みは、繋ぐ \(2\) 頂点に対応する点または円の間の距離とする。(\(2\) つの図形の距離は、端点がそれぞれの図形の上にあるような線分の長さの下限と定義する)

問題 : 辺をいくつか選び、タワーに対応する \(N\) 頂点が選んだ辺のみを使って互いに行き来可能であるようにするとき、選んだ辺の重みの合計の最小値を求めよ。

ここから、このようなグラフの構築の方法と、言い換え後の問題の解法に分けて解説します。

グラフの構築の仕方

辺の重みを求める方法を解説します。
まず、点は半径 \(0\) の円とみなすと実装が楽になります。この解説でも便宜上そのような見方をします。
\(2\) つの円の距離は以下のようになります。
\(2\) つの円の中心の距離を \(d\)、\(2\) つの円の半径をそれぞれ \(r_1, r_2\) とします。

• \(d \gt r_1 + r_2\) のとき :
  \(2\) つの円の距離は \(d - r_1 - r_2\) です。
  
• \(d \le r_1 + r_2\) かつ \(|r_1 - r_2| \gt d\) のとき
  片方の円が他方に包含されています。\(2\) つの円の距離は \(|r_1 - r_2| - d\) です。
  
• \(d \le r_1 + r_2\) かつ \(|r_1 - r_2| \le d\) のとき
  \(2\) つの円は共有点を持つため、距離は \(0\) です。

言い換え後の問題の解法

互いに行き来可能でなくてもよい \(M\) 個の頂点に注目します。
条件を満たすように辺を選んだ時、この \(M\) 個の頂点のうちいくつかは \(N\) 個の頂点と選んだ辺のみを使って行き来可能になります。
そのような頂点の集合 \(S\) を \(2^M\) 通り全探索します。
\(S\) が \(1\) つ決まったときの解法を考えます。
タワーに対応する \(N\) 頂点と \(S\) に含まれる頂点を合わせて \(T\) とします。
\(T\) 以外の頂点を片方でも端点に持つ辺は (\(N\) 個の頂点と行き来できないとした頂点が行き来できるようになってしまうため) 選んではいけない、または選んでも無意味に重みの和を増やすだけなので、選ばないとしてよいです。
すると、グラフから \(T\) に含まれない頂点を除去し、\(T\) 以外の頂点を片方でも端点に持つ辺も全て除去したグラフ (これを \(T\) による誘導グラフと呼びます) における最小全域木問題の答えが元の問題の答えです。
最小全域木問題はクラスカル法、プリム法などで解くことができます。
例えばクラスカル法を使った場合、この問題は全体で \(O(2^M(N + M)^2 \log(N + M))\) で解くことができます。