AtCoder Petrozavodsk Contest 001 D – Forest 连通块+并查集+贪心

D - Forest

My Solution

题意：给出一个由n个点m条边构成的森林，每个点有个权值val[i]，额外加一条边(u,v)的花费是val[u] + val[v]，且u、v只能被用到一次，添加一些边使得图连通，求最小花费。

连通块+并查集+贪心

可以先用并查集跑出连通块的个数为x，则需要添加的边的数量为x-1条，需要使用的点的个数为2*(x-1)，所以只要n>=2*(x-1)则必定有解。所以我们只要贪心的选出这2*(x-1)个点即可，故先在每个连通块选择一个权值最小的点，这样可以保证每个连通块都会有点和其它的连通块相连，然后剩余的2*(x-1) - x个点可以随便选，所以只要把没有用过的点排个序，选择最小的2*(x-1) - x个点即可。这里不要求具体的边，所以只要知道要用的点的集合即可不需要构造出边，故只要把这2*(x-1) - x个选出的点的权值求和即可。

时间复杂度 O(nlogn)

空间复杂度 O(n)

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
typedef pair<int, int> ii;
const int MAXN = 1e5 + 8;
 
 
priority_queue<ii, vector, greater> pq[MAXN];
int val[MAXN];
int fa[MAXN], _rank[MAXN];
inline void init(int n){
    for(int i = 0; i <= n; i++){
        fa[i] = i;
        _rank[i] = 0;
    }
}
inline int _find(int u){
    return fa[u] = fa[u] == u ? u : _find(fa[u]);
}
inline void _merge(int u, int v){
    int x = _find(u), y = _find(v);
    if(x == y) return;
    if(_rank[x] < _rank[y]){
        fa[x] = y;
    }
    else{
        fa[y] = x;
        if(_rank[x] == _rank[y]) _rank[x]++;
    }
}
 
vector vec;
int main()
{
    #ifdef LOCAL
    freopen("d.txt", "r", stdin);
    //freopen("d.out", "w", stdout);
    int T = 1;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n, m, i, u, v, findu, findv;
    LL ans = 0;
    cin >> n >> m;
    init(n);
    for(i = 0; i < n; i++){ cin >> val[i];
    }
    for(i = 0; i < m; i++){ cin >> u >> v;
        findu = _find(u), findv = _find(v);
        if(findu != findv){
            _merge(findu, findv);
        }
    }
    for(i = 0; i < n; i++){
        pq[_find(i)].push(ii(val[i], i));
    }
    for(i = 0; i < n; i++){
        if(!pq[i].empty()){
            vec.push_back(pq[i].top());
            val[pq[i].top().second] = 2e9;
            ans += pq[i].top().first;
        }
    }
    //cout << vec.size() << endl;
    if(vec.size() == 1){
        cout << 0 << endl;
    }
    else if(n < (vec.size()-1) * 2) cout << "Impossible" << endl;
    else{
        sort(val, val + n);
        n = (vec.size()-1) * 2 - vec.size();
 
        for(i = 0; i < n; i++){
            ans += val[i];
        }
        cout << ans << endl;
    }
 
 
 
    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

问题Source

AtCoder Petrozavodsk Contest 001

Thank you!

                                                                                                                                             ------from ProLightsfx