問題文

https://beta.atcoder.jp/contests/apc001/tasks/apc001_d

公式想定解法

考察すると次が分かる
- 各連結成分のうち，必ず使わなければならない頂点は 1 個
- 全て合わせて2(N-M-1)頂点使う．
ので，これを実装すれば良い．実装量はとても軽い．

以下，遠回り解法の解説

考察

連結成分がパスだろうがスターだろうが問題に関係しないことが分かる．
よって，入力データはGraphではなくUnionFindで持っておくと便利．
問題の『異なる頂点を選択し接合すると二度と使えなくなる』とは
- 2つの連結成分をマージして接合に使った頂点を除外する操作，と置き換えられる．
使う頂点の列挙ならば貪欲法でも成立しそう．
- つまり，最もweightが小さな頂点を使う方針は最適っぽい．

コーナーケース

愚直な貪欲で頂点を接合すると大変な事になるサンプル

8 4
999 1 2 3 4 999 99 99
0 1
2 3
4 5
6 7

連結成分の大きさが1の頂点同士を選ぶとImpoになってしまうサンプル

6 2
1 1 1 9 9 9
3 4
4 5

実装方針

ある連結成分があって，そこから頂点を1つ選択したいとき，必ずweight最小の頂点を選ぶ．
- 連結成分ごとに priority_queue で管理すれば良い．
  - priority_queue を連結成分数個用意する .
連結成分の大きさが1の連結成分
- 絶対にその頂点はweightに関わらず選択される
- よって，後回しで良い．
- 先に連結成分の大きさ2以上のもの同士を接合する．
- これでコーナー2は回避した .
連結成分の大きさ2以上のもの同士の接合
- この部分がかなり怪しい
- 連結成分ごとに『選ばれやすさ(Heuristics)』を定義する．
- 『選ばれやすさ』が高い連結成分を2つ選んで接合していくと良さそう．
- 『選ばれやすさ』とは何か
  - 『連結成分の中で最も軽い頂点のweight』とするとコーナー1が通らない
  - 『1番目と2番目に軽い頂点のweightの和』としたら通った

コード

コメント無いです

class Unionfind {
public:
    vector<int> data;
    Unionfind(size_t size) : data(size, -1) { }
    bool connect(size_t x, size_t y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = (int)x;
        }
        return x != y;
    }
    inline bool same(size_t x, size_t y) {
        return root(x) == root(y);
    }
    inline size_t root(size_t x) {
        return (size_t)(data[x] < 0 ? x : data[x] = root(data[x]));
    }
    inline int size(size_t x) {
        return -data[root(x)];
    }
};

inline ll top_two(priority_queue<ll>& pq) {
    ll t = pq.top(); pq.pop();
    ll s = t + pq.top();
    pq.push(t);
    return s;
}


ll m, n, kei;
ll aa[100010];

int main() {
    scanner >> n >> m;
    scanner.in(aa, aa + n);

    if (n == 1)
        bye("0");

    Unionfind uf(n);

    repeat(i, m) {
        int x, y;
        scanner >> x >> y;
        uf.connect(x, y);
    }

    priority_queue<pair<ll, int>> pq_1; // 後回しqueue．優先度関係ないのでstackに置き換えるべき
    priority_queue<pair<ll, int>> pq;

    vector<priority_queue<ll>> vq(n);
    repeat(i, n) {
        vq[uf.root(i)].push(-aa[i]);
    }
    repeat(i, n) {
        if (uf.root(i) == i) {
            if (vq[i].size() == 1)
                pq_1.emplace(vq[i].top(), i);
            else {
                pq.emplace(top_two(vq[i]), i);
            }
                
        }
    }

    ll ans = 0;

    while (1 < pq.size()) {
        auto p1 = pq.top(); pq.pop();
        auto p2 = pq.top(); pq.pop();

        ans += -vq[p1.second].top() - vq[p2.second].top();
        //cout << make_pair(-p1.first, -p2.first) << endl;

        if (vq[p1.second].size() < vq[p2.second].size())
            swap(p1, p2);
        {
            auto& q1 = vq[p1.second];
            auto& q2 = vq[p2.second];
            q1.pop(); q2.pop();
            // merge q1 << q2
            while (!q2.empty()) {
                q1.push(q2.top());
                q2.pop();
            }

            if (q1.size() == 1)
                pq_1.emplace(q1.top(), p1.second);
            else
                pq.emplace(top_two(q1), p1.second);
        }
    }

    while (!pq_1.empty()) {
        auto p1 = pq_1.top(); pq_1.pop();
        decltype(p1) p2;

        if (pq.empty()) {
            if (pq_1.empty())
                break;
            if (pq_1.size() != 1)
                bye("Impossible");
            p2 = pq_1.top(); pq_1.pop();
            ans += -vq[p1.second].top() - vq[p2.second].top();
            break;
        }
        else
            p2 = pq.top(); pq.pop();

        ans += -vq[p1.second].top() - vq[p2.second].top();
        //cout << make_pair(-p1.first, -p2.first) << endl;

        vq[p2.second].pop();

        if (vq[p2.second].size() == 1)
            pq_1.emplace(vq[p2.second].top(), p2.second);
        else
            pq.emplace(top_two(vq[p2.second]), p2.second);
    }

    cout << ans << endl;

    return 0;
}

buyoh.hateblo.jp

残念な競技プログラミング参加者による学習記録

AtCoder Petrozavodsk Contest 001 - D Forest

問題文

公式想定解法

以下，遠回り解法の解説

考察

コーナーケース

実装方針

コード