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

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

AtCoder Petrozavodsk Contest 001 D - Forest (600 点)

面白かった

問題へのリンク

問題概要

 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();
}