Cod sursa(job #1833147)

Utilizator radudurlesteanuDurlesteanu Radu Stefan radudurlesteanu Data 21 decembrie 2016 19:53:50
Problema Arbore partial de cost minim Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <cstdio>
#include <algorithm>
#define N 200001
using namespace std;
struct edge{
           int n1,n2,cost;
           }e[N*2],sol[N];
int f[N],h[N],n,m,nr,cost;

void read() {
int i;
freopen("apm.in","r",stdin);
scanf("%d%d",&n,&m);
for (i=0;i<m;++i)
scanf("%d%d%d",&e[i].n1,&e[i].n2,&e[i].cost);
}

inline bool cmp(const edge A,const edge B) {
return A.cost<B.cost;
}

inline int find(int node) {
while (f[node]) node=f[node];
return node;
}

void unite(int n1,int n2) {
if (h[n1]>h[n2]) f[n2]=n1;
else {
      f[n1]=n2;
      if (h[n1]==h[n2]) h[n2]++;
     }
}

void kruskal() {
int i,n1,n2,arb1,arb2;
for (i=1;i<=n;++i) h[i]=1;
sort(e,e+m,cmp);
i=nr=0;
while (nr<n-1)
    {
    n1=e[i].n1;n2=e[i].n2;
    arb1=find(n1);arb2=find(n2);
    if (arb1!=arb2) {
                     sol[nr].n1=n1;
                     sol[nr].n2=n2;
                     nr++;
                     cost+=e[i].cost;
                     unite(arb1,arb2);
                    }
    i++;
    }
}
void write() {
int i;
freopen("apm.out","w",stdout);
printf("%d\n%d\n",cost,nr);
for (i=0;i<nr;++i)
printf("%d %d\n",sol[i].n1,sol[i].n2);
}

int main()
{
read();
kruskal();
write();
return 0;
}