Pagini recente » Cod sursa (job #262046) | Cod sursa (job #1209097) | Cod sursa (job #1189058) | Cod sursa (job #883609) | Cod sursa (job #2979964)
#include <bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int rang[100005] , t[100005], viz[100005] , n , m ;
long long s;
struct muchie
{
int x , y , c;
}v[100005];
bool cmp(muchie a , muchie b)
{
return a.c < b.c;
}
int radacina ( int nod)
{
if(t[nod] == 0)
return nod;
else
{
int k = radacina(nod);
t[nod] = k;
return k;
}
}
void unire(int a , int b)
{
int ra = radacina(a);
int rb = radacina(b);
if(rang[ra] > rang[rb])
t[ra] = rb;
else
t[rb] = ra;
if(rang[ra] < rang[rb])
rang[rb]++;
}
int main()
{
f >> n >> m;
for ( int i = 1; i <= m ; i++)
{
f >> v[i].x >> v[i].y >> v[i].c;
}
sort ( v + 1 , v + m + 1 , cmp);
for ( int i = 1 ; i <= m ; i++)
{
int a = v[i].x , b = v[i].y , cost = v[i].c;
if(radacina(a) != radacina(b))
{
s = s + cost;
unire(a,b);
}
}
g << s;
}