Pagini recente » Cod sursa (job #2593563) | Cod sursa (job #1786376) | Cod sursa (job #504114) | Cod sursa (job #283661) | Cod sursa (job #229317)
Cod sursa(job #229317)
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn = 400100;
int GR[maxn],X[maxn],Y[maxn],C[maxn];
int N,M,ANS,IND[maxn];
int grupa(int i)
{
if (GR[i] == i) return i;
GR[i] = grupa(GR[i]);
return GR[i];
}
void reuniune(int i,int j)
{
GR[grupa(i)] = grupa(j);
}
bool cmpf(int i,int j)
{
return(C[i] < C[j]);
}
int main()
{
freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);
scanf("%d %d\n",&N,&M);
for(int i = 1;i <= M;++i)
{
scanf("%d %d %d\n",&X[i],&Y[i],&C[i]);
IND[i] = i;
}
for(int i = 1;i <= N; ++i) GR[i] = i;
sort(IND + 1,IND + M + 1,cmpf);
for(int i = 1;i <= M; ++i)
{
if (grupa(X[IND[i]]) != grupa(Y[IND[i]])){ANS += C[IND[i]];reuniune(X[IND[i]],Y[IND[i]]);}
}
printf("%d\n",ANS);
return 0;
}