Pagini recente » Cod sursa (job #1179118) | Cod sursa (job #2875291) | Cod sursa (job #2797038) | Cod sursa (job #138776) | Cod sursa (job #3222071)
#include <iostream>
#include <fstream>
#include <algorithm>
#define nMax 200001
#define mMax 400001
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie{
int x, y, cost;
}muchii[mMax];
int n, m, grupe[nMax], s;
void init(){
for(int i=1;i<=n;i++)
grupe[i]=i;
}
bool cmpMuchii(muchie a, muchie b){
return a.cost<b.cost;
}
int find(int x) {
if (grupe[x] == x)
return x;
return grupe[x] = find(grupe[x]);
}
void unite(int x, int y) {
int setX, setY;
setX = find(x);
setY = find(y);
if (setX != setY)
grupe[setX] = setY;
}
int main()
{
fin>>n>>m;
init();
for(int i=1;i<=m;i++)
fin>>muchii[i].x>>muchii[i].y>>muchii[i].cost;
std::sort(muchii+1, muchii+1+m, cmpMuchii);
for (int i=1;i<=m;i++)
if (find(muchii[i].x) != find(muchii[i].y)) {
unite(muchii[i].x, muchii[i].y);
s += muchii[i].cost;
}
fout<<s;
return 0;
}