面白かった

問題概要

$N$ 頂点 $M$ 辺の森が与えられる。各頂点 $v$ には、値 $a_{v}$ が付いている。これにいくつかの辺を追加して、連結にしたい。

頂点 $i$ と頂点 $j$ とを結ぶのに必要なコストは $a_{i} + a_{j}$ である
すでに辺がある二頂点間は結べない
一度辺を張るのに使用した頂点は、他の頂点と結ぶことはできない

連結するための最小コストを求めよ。不可能な場合は "Impossible" と出力せよ。

制約

$1 \le N \le 10^{5}$

考えたこと

こういうのはいかにも Wrong Answer を出しそうで怖い。慎重にちゃんと証明しながらやりたい...

まず、可能な条件を考えたい。森の各連結成分のサイズを $c_{1}, \dots, c_{K}$ とする。 $c_{1} + \dots + c_{K} = N$ という制約はあるものの、ある程度自由な値をとれるものである。

極端な話、 $c$ がすべて 0 の場合はダメ。もう少し具体的には、

$c$ の総和 < $2(K-1)$

のときはダメ。なぜなら、辺を $K-1$ 本張る必要があるため。そして逆に、 $c$ の総和が $2(K-1)$ 以上のときは連結にすることが可能である！！！

具体的には、合計 $2(K-1)$ 個の頂点を、どの連結成分からも最低 1 個ずつは選ばれるように選んであげて、それらを適切にペアリングしてあげればよい。

具体的な最小コストは、

各連結成分から、まずは 1 個ずつ「コスト最小の頂点」を選ぶ
その後は残りの頂点からコストが小さい順に、 $K-2$ 個選ぶ

とすれば OK。注意点として、 $K = 1$ の場合は例外で、はじめから 0 を出力しておく。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1LL<<60;
using Graph = vector<vector<int>>;
int N, M;
Graph G;
vector<long long> a;

void rec(int v, vector<bool> &seen, vector<int> &comp) {
    seen[v] = true;
    for (auto e : G[v]) {
        if (seen[e]) continue;
        rec(e, seen, comp);
    }
    comp.push_back(v);
}

void solve() {
    vector<vector<int>> comps;
    vector<bool> seen(N, false);
    for (int v = 0; v < N; ++v) {
        if (seen[v]) continue;
        vector<int> comp;
        rec(v, seen, comp);
        comps.push_back(comp);
    }

    int sum = 0;
    for (auto comp : comps) sum += (int)comp.size() - 1;
    if (sum < (int)comps.size()-2) {
        cout << "Impossible" << endl;
        return;
    }
    if (comps.size() == 1) {
        cout << 0 << endl;
        return;
    }

    long long res = 0;
    vector<long long> rem;
    for (auto comp : comps) {
        long long mi = INF;
        int pmi = -1;
        for (int i = 0; i < comp.size(); ++i) {
            if (chmin(mi, a[comp[i]])) pmi = i;
        }
        res += mi;
        for (int i = 0; i < comp.size(); ++i) {
            if (i == pmi) continue;
            rem.push_back(a[comp[i]]);
        }
    }
    sort(rem.begin(), rem.end());
    int V = comps.size();
    for (int i = 0; i < V-2; ++i) res += rem[i];
    cout << res << endl;
}

int main() {
    cin >> N >> M;
    a.resize(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    G.assign(N, vector<int>());
    for (int i = 0; i < M; ++i) {
        int x, y; cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    solve();
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder Petrozavodsk Contest 001 D - Forest (青色, 600 点)

問題概要

制約

考えたこと