题解 CF1095F 【Make It Connected】

· · 题解

Description

给定 n 个点，每个点有点权，连结两个点花费的代价为两点的点权和。另外有 m 条特殊边，参数为 x,y,z。意为如果你选择这条边，就可以花费 z 的代价将点 x 和点 y 连结起来，当然你也可以不选择这条边。求使整个图联通的最小代价

Input

第一行是两个整数，分别是点数 n 和特殊边的数量 m

下面一行 n 个数，第 i 个数代表点 i 的点权

下面 m 行，每行三个数 x,y,z，代表一条特殊边

Output

输出一行一个整数，最小代价

Hint

1~\leq~n~\leq~2~\times~10^5~,0~\leq~m~\leq~2~\times~10^5

设第 i 个点的点权为 a_i，第 j 条特殊边的边权为 z_j，保证

1~\leq~a_i,z_j~\leq~10^{12}

保证特殊边的参数 x~\neq~y

Solution

显然这个题目是要求一个 MST (最小生成树)，但是 O(n^2) 建图显然不可取。

我们考虑克鲁斯卡尔算法的本质：

有若干个联通块，每次寻找联通块间权值最小的边将之连结。

考虑对于本题来说，在不考虑特殊边的情况下，连结两个联通块，显然要分别选择两个联通块内点权最小的点连结。于是我们对每个集合维护点权最小的点，每次取出点权前两小的集合进行连边即可。维护点权前两小的集合显然可以用一个堆做。

考虑有特殊边怎么办：

我们把特殊边排序，每次比较当前的特殊边的权值小还是前两个联通块的点权小，选择更小的合并。

注意处理一下当前选出的两个点在一个集合中的情况。

因为一共要做 O(n) 次，每次会有 O(1) 次对堆的插入和删除操作，于是复杂度 O(n \log n)

Code

#include <cstdio>
#include <queue>
#include <algorithm>
#ifdef ONLINE_JUDGE
#define freopen(a, b, c)
#endif
#define rg register
#define ci const int
#define cl const long long

typedef long long int ll;

namespace IPT {
    const int L = 1000000;
    char buf[L], *front=buf, *end=buf;
    char GetChar() {
        if (front == end) {
            end = buf + fread(front = buf, 1, L, stdin);
            if (front == end) return -1;
        }
        return *(front++);
    }
}

template <typename T>
inline void qr(T &x) {
    rg char ch = IPT::GetChar(), lst = ' ';
    while ((ch > '9') || (ch < '0')) lst = ch, ch=IPT::GetChar();
    while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = IPT::GetChar();
    if (lst == '-') x = -x;
}

template <typename T>
inline void ReadDb(T &x) {
    rg char ch = IPT::GetChar(), lst = ' ';
    while ((ch > '9') || (ch < '0')) lst = ch, ch = IPT::GetChar();
    while ((ch >= '0') && (ch <= '9')) x = x * 10 + (ch ^ 48), ch = IPT::GetChar();
    if (ch == '.') {
        ch = IPT::GetChar();
        double base = 1;
        while ((ch >= '0') && (ch <= '9')) x += (ch ^ 48) * ((base *= 0.1)), ch = IPT::GetChar();
    }
    if (lst == '-') x = -x;
}

namespace OPT {
    char buf[120];
}

template <typename T>
inline void qw(T x, const char aft, const bool pt) {
    if (x < 0) {x = -x, putchar('-');}
    rg int top=0;
    do {OPT::buf[++top] = x % 10 + '0';} while (x /= 10);
    while (top) putchar(OPT::buf[top--]);
    if (pt) putchar(aft);
}

const int maxn = 200010;
const int maxm = 400010;

struct Edge {
    int from, to;
    ll v;
    inline bool operator<(const Edge &_others) const {
        return this->v < _others.v;
    }
};
Edge edge[maxm];

int n, m;
int ufs[maxn], vec[maxn], rk[maxn];
ll ans;
ll MU[maxn];

struct Zay {
    int id;
    ll v;
    inline bool operator<(const Zay &_others) const {
        return this->v > _others.v;
    }
};
std::priority_queue<Zay>Q;

int find(ci x) {return ufs[x] == x ? x : ufs[x] = find(ufs[x]);}

int main() {
    freopen("1.in", "r", stdin);
    qr(n); qr(m);
    for (rg int i = 1; i <= n; ++i) qr(MU[i]);
    for (rg int i = 1; i <= m; ++i) {
        qr(edge[i].from); qr(edge[i].to); qr(edge[i].v);
    }
    std::sort(edge + 1, edge + 1 + m);
    edge[m + 1].v = 1ll << 62;
    for (rg int i = 1; i <= n; ++i) ufs[i] = i, vec[i] = i, rk[i] = 1, Q.push((Zay){i, MU[i]});
    for (rg int i = 1, cur = 1; i < n; ++i) {
        while ((cur <= m) && (find(edge[cur].from) == find(edge[cur].to))) ++cur;
        Zay t1 = Q.top(); Q.pop(); Zay t2 = Q.top(); Q.pop();
        while (find(t1.id) == find(t2.id)) {t2 = Q.top(); Q.pop();}
        if ((t1.v + t2.v) <= edge[cur].v) {
            int fa = find(t1.id), fb = find(t2.id);
            ans += t1.v + t2.v;
            if (rk[fa] < rk[fb]) ufs[fb] = fa;
            else if (rk[fa] > rk[fb]) ufs[fa] = fb;
            else ufs[fa] = fb, ++rk[fb];
            Q.push((Zay){find(fa), t1.v});
            vec[find(fa)] = vec[fa];
        } else {
            int fa = find(edge[cur].from), fb = find(edge[cur].to);
            ans += edge[cur].v;
            if (rk[fa] < rk[fb]) ufs[fb] = fa;
            else if (rk[fa] > rk[fb]) ufs[fa] = fb;
            else ufs[fa] = fb, ++rk[fb];
            Q.push((Zay){find(fa), MU[vec[fa]]});
            vec[find(fa)] = vec[fa];
            Q.push(t1); Q.push(t2);
        }
    }
    qw(ans, '\n', true);
    return 0;
}