グラデーション / Gradation [第一回 アルゴリズム実技検定 過去問 L]

https://atcoder.jp/contests/past201912-open/tasks/past201912_l

前提知識

• 最小全域木

解説

https://atcoder.jp/contests/past201912-open/submissions/9258479

条件も多くて大変そう。
似ているアルゴリズムを考えると、最小全域木であるが、0＜Mなのでどうしようかという感じ。
Mがなくなれば解けそうだが、先にMの可能性を潰すというのも難しそう。
他に使えそうな感じというと、色の種類が3種類しかない。
…
いや、これ難しくない？？？

まあ、冷静に考えると、最小全域木に帰着できるんだろうなという所は譲れない。
ここがなくなると考える道筋がなくなる。
そうすると邪魔なのが、小さな塔の扱いである。
連結する小さい塔が分かっていれば、あとは最小全域木になる。
あぁ、これだ。

ポエムはこの辺にして、以下解法。
最小全域木の求め方が分からない方は、ググって勉強してこよう。
そちらが理解できていないとこちらは分からないし、この問題は入門には向かない。
小さな塔で使うものの組み合わせを全列挙する。
これで、連結させたい頂点が全て揃うので、全ての頂点間に辺があると考えて、最小全域木を探す。
この中で最小コストのものが答え。

int N, M, X[40], Y[40], C[40];
//---------------------------------------------------------------------------------------------------
double solve(int msk) {
    vector<int> points;
    rep(i, 0, N) points.push_back(i);
    rep(i, 0, M) if (msk & (1 << i)) points.push_back(i + N);
    int n = points.size();

    vector<pair<double, pair<int, int>>> edges;
    rep(i, 0, n) rep(j, i + 1, n) {
        int a = points[i];
        int b = points[j];
        double dx = X[a] - X[b];
        double dy = Y[a] - Y[b];
        double d = sqrt(dx * dx + dy * dy);
        if (C[a] != C[b]) d *= 10;
        edges.push_back({ d, {i, j} });
    }
    sort(all(edges));

    UnionFind uf(n);
    double ans = 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);
            ans += cst;
        }
    }
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> X[i] >> Y[i] >> C[i];
    rep(i, 0, M) cin >> X[i + N] >> Y[i + N] >> C[i + N];

    double ans = 1e30;
    rep(msk, 0, 1 << M) chmin(ans, solve(msk));
    printf("%.12f\n", ans);
}