Cod sursa(job #2351375)

Utilizator smatei16Matei Staicu smatei16 Data 22 februarie 2019 12:23:39
Problema Arbore partial de cost minim Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <cstdio>
#include <algorithm>
using namespace std;
struct nod{
int x,y,c;};
nod e[400005];
bool cmp(nod i,nod j){
return (i.c<j.c);
}
int n,m,i,j,l[200005],cost,nr,h,p,a[200005],b[200005],z;
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",&e[i].x,&e[i].y,&e[i].c);
    cost=0;
    for(i=1;i<=n;i++)l[i]=i;
    sort(e+1,e+m+1,cmp);
    i=1;nr=0;
    while(i<=m && nr<n-1){
        if(l[e[i].x]!=l[e[i].y]){
            cost+=e[i].c;
            nr++;
            z++;
            a[z]=e[i].x;
            b[z]=e[i].y;
            h=l[e[i].x];p=l[e[i].y];
            for(j=1;j<=n;j++)
                if(l[j]==h)l[j]=p;
        }
        i++;
    }
    printf("%d\n%d\n",cost,z);
    for(i=1;i<=z;i++)
        printf("%d %d\n",a[i],b[i]);

    return 0;
}