Cod sursa(job #698554)

Utilizator hiticas_abelhiticasabel hiticas_abel Data 29 februarie 2012 14:49:35
Problema Arbore partial de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
 using namespace std;
 const int maxn=400100;
 int gr[maxn],x[maxn],y[maxn],cost[maxn];
 int n,m,rez,indice[maxn];
 vector<int> apm;
 
 int padure (int i)
 {
    if(gr[i]==i) return i;
    gr[i]=padure(gr[i]);
     return gr[i];
 } 
 
 void reuniune (int i,int j)
 {
    gr[padure(i)]=padure(j);     
 
 }
 bool cmp(int i, int j)
 {
   return (cost[i]<cost[j]);     
 }
 
 int main()
 {
 freopen( "subarbore.in","r",stdin);
 freopen ("subarbore.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],&cost[i]);
                   indice[i]=i;
                   
     }  
     for(int i=1;i<=n;i++)
     
     gr[i]=i;
     sort(indice+1,indice+1+m,cmp);
     
     for(int i=1;i<=m;i++)
     {
     if(padure(x[indice[i]])!=padure(y[indice[i]]))
     {
     rez+=cost[indice[i]];
     reuniune(x[indice[i]],y[indice[i]]);
     apm.push_back(indice[i]);
                                                   
     }        
     }
     printf("%d \n",rez);
    // printf("%d\n",n-1);
    // for(int i=0;i<n-1;i++)
   //  printf("%d %d \n",x[apm[i]], y[apm[i]]);
     return 0;
     
 }