UPGRANET (2) - VOI 11 (Nâng cấp mạng)

#include <bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1e5 + 5;

struct edge {
    int c, u, v;
};

bool operator < (const edge &a, const edge &b) {
    return a.c > b.c;
}

struct dsu {
    int *parent;

    dsu(int n): parent(new int[n+1]) {
        iota(parent + 1, parent + n + 1, 1);
    }

    int findd(int u) {
        if(parent[u] != u)
            parent[u] = findd(parent[u]);
        return parent[u];
    }

    void join(int u, int v) {
        if(rand()&1) swap(u, v);
        parent[findd(u)] = findd(v);
    }
};

namespace lca {
    LL res = 0;
    int n, parent[N], c[N];
    bool color[N];
    vector<int> queries[N];

    struct pack {
        int c, v;
    };
    vector<pack> ke[N];

    struct queue_type {
        int u, v;
    };
    vector<queue_type> queue[N];

    int find(int u) {
        if(parent[u] != u) {
            int tmp = parent[u];
            parent[u] = find(parent[u]);
            c[u] = min(c[u], c[tmp]);
        }
        return parent[u];
    }

    void dfs(int u, int dad) {
        parent[u] = u;
        for(pack p : ke[u])
                if (p.v != dad) {
                dfs(p.v, u);
                parent[p.v] = u;
                c[p.v] = p.c;
            }
        color[u] = true;

        for(int v : queries[u])
            if (color[v] == true)
                queue[find(v)].push_back({u, v});

        for(auto q : queue[u]) {
            find(q.u), find(q.v);
            res += min(c[q.u], c[q.v]);
        }
    }

    void solve() {
        fill(c + 1, c + n + 1, 1e9);
        dfs(1, 0);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m; cin >> n >> m;
    vector<edge> edges(m);

    for(edge &e : edges)
        cin >> e.u >> e.v >> e.c;

    sort(edges.begin(), edges.end());
    dsu d(n);

    LL res = 0;
    for(edge &e : edges)
        if(d.findd(e.u) != d.findd(e.v)) {
            d.join(e.u, e.v);
            lca::ke[e.u].push_back({e.c, e.v});
            lca::ke[e.v].push_back({e.c, e.u});
        }
        else {
            res += e.c;
            lca::queries[e.u].push_back(e.v);
            lca::queries[e.v].push_back(e.u);
        }

    lca::n = n;
    lca::solve();
    cout << lca::res - res;

    return 0;
}