Pagini recente » Cod sursa (job #2668552) | Cod sursa (job #3002052) | Cod sursa (job #1693199) | Cod sursa (job #1775870) | Cod sursa (job #830672)
Cod sursa(job #830672)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,i,j,k,m,viz[200005],a,b,aa[200005],bb[200005],rez,r1,r2;
long long rezz;
struct nod
{
int x;
int y;
int cost;
}v[200005];
int cmp(const nod a,const nod b)
{
return a.cost<b.cost;
}
int find(int t)
{
while(viz[t]!=0) t=viz[t];
return t;
}
int main()
{
freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);
scanf("%d %d",&n,&m);
for (i=1;i<=m;i++) scanf("%d %d %d",&v[i].x,&v[i].y,&v[i].cost);
sort(v+1,v+m+1,cmp);
for (i=1;i<=m;i++) if (find(v[i].x)!=find(v[i].y))
{
rezz=rezz+v[i].cost;
r1=find(v[i].x),r2=find(v[i].y);
if (r1>r2) viz[r2]=r1;else viz[r1]=r2;
rez++;
aa[rez]=v[i].x;
bb[rez]=v[i].y;
}
printf("%lld\n",rezz);
printf("%d\n",rez);
for (i=1;i<=rez;i++)printf("%d %d\n",bb[i],aa[i]);
return 0;
}