AtCoderPetrozavodskContest001D-Forest连通块+并查集+贪心

D - Forest

---

Time limit: 2sec /Memory limit: 256MB

Score :600points

Problem Statement

You are given a forest withNvertices andMedges. The vertices are numbered0throughN?1. The edges are given in the format(xi,yi), which means that Vertexxiandyiare connected by an edge.

Each vertexihas a valueai. You want to add edges in the given forest so that the forest becomes connected. To add an edge, you choose two different verticesiandj, then span an edge betweeniandj. This operation costsai+ajdollars, and afterward neither Vertexinorjcan be selected again.

Find the minimum total cost required to make the forest connected, or printImpossibleif it is impossible.

Constraints

1≤N≤100,000

0≤M≤N?1

1≤ai≤109

0≤xi,yi≤N?1

The given graph is a forest.

All input values are integers.

---

Input

Input is given from Standard Input in the following format:

N M
a0 a1 .. aN?1
x1 y1
x2 y2
:
xM yM

Output

Print the minimum total cost required to make the forest connected, or printImpossibleif it is impossible.

---

Sample Input 1

Copy

7 5
1 2 3 4 5 6 7
3 0
4 0
1 2
1 3
5 6

Sample Output 1

Copy

7

If we connect vertices0and5, the graph becomes connected, for the cost of1+6=7dollars.

---

Sample Input 2

Copy

5 0
3 1 4 1 5

Sample Output 2

Copy

Impossible

We can't make the graph connected.

---

Sample Input 3

Copy

1 0
5

Sample Output 3

Copy

0

The graph is already connected, so we do not need to add any edges.

Source

AtCoder Petrozavodsk Contest 001

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 ii;
const int MAXN = 1e5 + 8;
 
 
priority_queue, 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;
}