Pagini recente » Borderou de evaluare (job #3206502) | Istoria paginii info-oltenia-2018/individual/10 | Cod sursa (job #748190) | Cod sursa (job #1893510) | Cod sursa (job #2704194)
#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;
}