APC001 D - Forest (600)

森に枝を挿すと木になる

問題概要

N頂点M辺の森が与えられます。頂点には0から N−1の番号がついています。辺(xi, yi)は頂点xiとyiをつなげています。 各頂点iには aiという値が定まっています。 あなたは与えられた森に辺を追加して連結にしたいです。 辺を追加するときには、まず異なる頂点二つを選択し(i,jとする)、iとjの間に辺を張ります。 この時コストがai+ajかかります。そしてこれ以降，頂点iとjは永遠に選択できなくなります。 森を連結にする最小コストを求めてください。 連結にするのが不可能な場合は"Impossible"と出力してください。

制約

• 
• 
• 
• 

解法

全体を連結にする最小コストを求めたいので最小全域木で解けないか考えますが、これはうまくいきません。この問題では頂点に重みがあり、しかも一度使った頂点は2度使用できないという制約があります。これを最小全域木の問題に落とし込むのは難しいと思います。

コストのことは置いておいて、まず全体を連結にできるかどうかを考えます。

すでに連結になっているこころに新たに辺を追加する必要はありません。なのでまだ連結でない連結成分同士を辺で結ぶことを考えます。ここで連結成分をひとつの頂点としてみなすと見通しがよくなります。連結成分から伸ばせる辺は含む頂点数になります。すると問題のグラフを次数の制限を持ついくつかの頂点の集合に置き換えられます。

K頂点を連結にするためには最低K-1辺必要なことが知られています。また1つの辺につき次数が2あることを考えると全体で消費する次数は2*(K-1)になります。

よって先ほど置き換えたグラフの頂点数をKとすると、その次数の総和が少なくとも2*(K-1)以上でないと全体を連結にできないことがわかります。逆に次数が2*(K-1)以上であれば全体を連結にできることがわかります。(星形から考えるとわかりやすい)

次にコストを最小にする辺のつなぎ方を考えます。

2つの連結成分を辺でつなぐときコストの大きい頂点を選ぶ利点はないのでそれぞれの成分内で最もコストの小さい頂点を貪欲に選べばいいです。ということで頂点をコストでソートして小さい順に使えばよさそうですが、各連結成分で少なくとも1つは頂点を使わないといけないので先にこれを決めておきます。残りを貪欲すれば答えになります。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MAX_N = int(1e5 + 5);

struct UnionFindTree {
    vector<int> par;
    vector<int> rank;
    vector<int> siz;

    void init(int n) {
        par.resize(n);
        rank.resize(n);
        siz.resize(n);
        for (int i = 0; i < n; i++) {
            par[i] = i;
            rank[i] = 0;
            siz[i] = 1;
        }
    }
    int find(int x) {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = find(par[x]);
        }
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) rank[x]++;
        par[y] = x;
        siz[x] += siz[y];
    }
    bool is_same(int x, int y) {
        return find(x) == find(y);
    }
    int size(int x) {
        x = find(x);
        return siz[x];
    }
};

int n, m;
P a[MAX_N];
UnionFindTree g;
map<int, int> deg;
bool used[MAX_N]{};
vector<ll> v;

int main() {
    cin >> n >> m;
    for(int i=0; i<n; i++){
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a,a+n);
    g.init(n);
    for(int i=0; i<m; i++){
        int x, y;
        cin >> x >> y;
        g.unite(x,y);
    }
    int dsum = 0;
    for(int i=0; i<n; i++){
        if(deg.count(g.find(i))==0){
            deg[g.find(i)] = g.size(i);  // 連結成分を1つの頂点とみなす。次数の制限は含む頂点数となる。
            dsum += g.size(i);
        }
    }
    if((deg.size()-1)*2 > dsum){ // 次数は辺の2倍必要
        cout << "Impossible" << endl;
    }
    else if(deg.size()==1){
        cout << 0 << endl;
    }
    else{
        ll ans = 0;
        for(int i=0; i<n; i++){
            int x = g.find(a[i].second);
            if(!used[x]){  // 1頂点につき最低1次数は使う
                used[x] = true;
                ans += a[i].first;
                deg[x]--;
            }
            else if(deg[x]>0){
                v.push_back(a[i].first);
                deg[x]--;
            }
        }
        for(int i=0; i<int(deg.size()-2); i++){
            ans += v[i];
        }
        cout << ans << endl;
    }
    return 0;
}

コメント

ところどころ証明しろと言われると厳しい...