Urban Planning [第六回 アルゴリズム実技検定 L]

https://atcoder.jp/contests/past202104-open/tasks/past202104_l

前提知識

• 最小全域木
• （幾何）

解説

https://atcoder.jp/contests/past202104-open/submissions/22659267

ICPCでよく見るような幾何問題。
幾何問題といっても特殊な知識を要求するものではないが、円とか距離とかちょっと大変かなと思う。

さて、何から始めようか。

環状交差点が無ければ

もし、環状交差点が無ければどうだろう。
点が与えられて各点に辺を貼って、連結になるようにその辺を選択していくことになる。
辺のコストは各点の距離となる。
自分は幾何ライブラリを持っているので、ここはベクトル計算っぽくやった。
どんな考え方でやっても立式は同じになるだろうし、あまり細かく説明しない。

ここで重要なのが、連結になるように辺を選択していく部分にある。
このように、連結になるように辺を選択して全体を連結にするような問題を「最小全域木」という。
最小全域木についてよくわからない場合はどこかで勉強してくるといい。
プリム法とクラスカル法のどちらでも大丈夫だが、自分の実装はクラスカル法でやっている。

環状交差点があったらどうだ？

無かった場合はタワー間での距離を考えたが、これも同様である。
環状交差点間と環状交差点とタワー間での距離を考えて同様にクラスカル法をやればいい。
だが、注意点が増える。

最短距離

最短距離計算がグンと難しくなる。
環状交差点とタワー間、環状交差点間の距離計算が増えるが、タワーを中心だけあって半径0として考えれば1つアルゴリズムで済む。
こうすれば、タワー間も同様のアルゴリズムで計算ができる。
実装が大変だろうなぁと予測できたら、なるべく簡単な方針を考えてみよう。

getDistで実装している。
実装通りという感じではあるのだが、横並びで離れてるとき、交差しているとき、包含されているときで場合分けして計算する。

環状交差点が連結である必要はない

最小全域木問題を解くが、連結が要求されているのはタワーだけである。
なので、環状交差点全てが連結である場合は最適ではない可能性がある。
しかも環状交差点間での結合をうまく扱うのが難しく、そのまま解けない。

解けないのだが、今回は環状交差点の数が少ないので、どれを使うかを全探索しよう。
使う環状交差点をbit全探索して、それぞれの場合でそれを使った場合の最小全域木を解こう。
これで解けた。

int N, M;
P towers[50];
P crossCenter[8]; double crossRedius[8];
//---------------------------------------------------------------------------------------------------
double getDist(P c1, double r1, P c2, double r2) {
    double dist = abs(c1 - c2);

    if (r1 + r2 < dist) return dist - r1 - r2;
    if (dist < abs(r1 - r2)) return abs(r1 - r2) - dist;
    else return 0;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) {
        int x, y; cin >> x >> y;
        towers[i] = P(x, y);
    }
    rep(i, 0, M) {
        int x, y, r; cin >> x >> y >> r;
        crossCenter[i] = P(x, y);
        crossRedius[i] = r;
    }

    double ans = inf;
    rep(msk, 0, 1 << M) {
        vector<pair<double, pair<int, int>>> edges;
        rep(i, 0, N) rep(j, i + 1, N) edges.push_back({ getDist(towers[i], 0, towers[j], 0), {i, j} });
        rep(i, 0, N) rep(j, 0, M) if (msk & (1 << j)) edges.push_back({ getDist(towers[i], 0, crossCenter[j], crossRedius[j]), {i, j + N} });
        rep(i, 0, M) if (msk & (1 << i)) rep(j, i + 1, M) if (msk & (1 << j)) {
            edges.push_back({ getDist(crossCenter[i], crossRedius[i], crossCenter[j], crossRedius[j]), {i + N, j + N} });
        }

        sort(all(edges));

        UnionFind uf(N + M);
        double tot = 0;
        fore(p, edges) {
            double cst = p.first;
            int a = p.second.first;
            int b = p.second.second;

            if (uf[a] != uf[b]) {
                uf(a, b);
                tot += cst;
            }

            set<int> parents;
            rep(i, 0, N) parents.insert(uf[i]);
            if (parents.size() == 1) chmin(ans, tot);
        }
    }

    printf("%.11f\n", ans);
}