# Cod sursa(job #1999113)

Utilizator Data 10 iulie 2017 12:48:48 Arbore partial de cost minim 100 cpp done Arhiva educationala 1.23 kb
``````#include <cstdio>
#include<algorithm>
using namespace std;
struct copaci
{
int x,y,c;
}apm[400005];
int t[200005],h[200005];
bool cmp(copaci a,copaci b)
{
return a.c<b.c;
}
int findMD(int x)
{
while(x!=t[x])
x=t[x];
return x;
}
bool unionMD(int x,int y)
{
int tx,ty;
tx=findMD(x);
ty=findMD(y);
if(tx==ty)
return 0;
if(h[tx]==h[ty])
{
h[tx]++;
t[ty]=tx;
}
else
if(h[tx]<h[ty])
t[tx]=ty;
else
t[ty]=tx;
return 1;
}
int main()
{
freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);
int n,m,i,tx,ty,tc;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&tx,&ty,&tc);
apm[i].x=tx;
apm[i].y=ty;
apm[i].c=tc;
}
for(i=1;i<=n;i++)
{
t[i]=i;
h[i]=1;
}
sort(apm+1,apm+m+1,cmp);
int cost=0;
for(i=1;i<=m;i++)
{
if(unionMD(apm[i].x,apm[i].y)==1)
cost=cost+apm[i].c;
else
apm[i].x=apm[i].y=0;
}
printf("%d\n%d\n",cost,n-1);
for(i=1;i<=m;i++)
if(apm[i].x!=0)
printf("%d %d\n",apm[i].y,apm[i].x);
return 0;
}
``````