Cod sursa(job #2704194)

Utilizator KOTOAMATSUKAMIDistinguished Heavenly Gods KOTOAMATSUKAMI Data 9 februarie 2021 22:10:05
Problema Arbore partial de cost minim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>
using namespace std;

struct muchie {
    int to, from, cost;
    muchie(const int &_to, const int &_from, const int &_cost) : to(_to), from(_from), cost(_cost) {}
    bool operator < (const muchie &x) const {
        return cost < x.cost;
    }
}; vector <muchie> M;

const int N(2e5);
int father[N + 1];
int parent(int x) {
    if (!father[x])
        return x;
    return father[x] = parent(father[x]);
}

void join(int x, int y) {
    x = parent(x);
    y = parent(y);
    if (x != y)
        father[x] = y;
}

int main() {
    ifstream fin("apm.in");
    ofstream fout("apm.out");

    int n, m;
    fin >> n >> m;

    int i, j, c;
    for (; m; --m) {
        fin >> i >> j >> c;
        M.emplace_back(i, j, c);
    } sort(M.begin(), M.end());

    int ans = 0;
    for (auto &it: M)
        if (parent(it.from) != parent(it.to)) {
            ans += it.cost;
            join(it.from, it.to);
        }

    fout << ans;
    return 0;
}