Submission #2087088

---

Source Code Expand

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
using namespace std;

typedef long long ll;
typedef pair<ll, int> P;
int n;
int m;

ll a[100010];
vector<int> edges[100010];

vector<priority_queue<ll,vector<ll>,greater<ll>>> tree;

void dfs()
{
    vector<bool> vis(n,false);

    for (int i = 0; i < n;i++)
    {
        if(vis[i] == false)
        {
            tree.push_back(priority_queue<ll,vector<ll>,greater<ll>>());
            priority_queue<ll,vector<ll>,greater<ll>> &now = tree[tree.size() - 1];
            queue<int> que;
            que.push(i);

            while(!que.empty())
            {
                int v = que.front();
                que.pop();

                if(vis[v]) continue;
                vis[v] = true;
                now.push(a[v]);

                for(int to : edges[v])
                {
                    que.push(to);
                }
            }
        }
    }
}

int main()
{
    cin >> n >> m;

    for (int i = 0; i < n;i++)
        cin >> a[i];

    for (int i = 0; i < m;i++)
    {
        int x, y;

        cin >> x >> y;

        edges[x].push_back(y);
        edges[y].push_back(x);
    }

    dfs();

    ll result = 0;
    priority_queue<ll,vector<ll>,greater<ll>> vec;
    int cou = n - m - 1;
    cou *= 2;
    if(cou == 0)
    {
        cout << 0 << endl;
        return 0;
    }
    for (int i = 0; i < tree.size();i++)
    {
        result += tree[i].top();
        tree[i].pop();
        cou--;
        while(!tree[i].empty())
        {
            vec.push(tree[i].top());
            tree[i].pop();
        }
    }

    while(cou > 0 && !vec.empty())
    {
        result += vec.top();
        vec.pop();
        cou--;
    }

    if(cou > 0)
    {
        cout << "Impossible" << endl;
        return 0;
    }

    cout << result << endl;

    return 0;
}

Submission Info

Judge Result