Cod sursa(job #1008140)

Utilizator x3medima17Dima Savva x3medima17 Data 10 octombrie 2013 12:24:42
Problema Arbore partial de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.6 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct vector{
       short x,y,val;
       };

class FX{
public:
      void sort(int l, int r, vector *vectors)
       {

            int i = l;
            int j = r;
            int x = vectors[(l+r)/2].val;
            do{
                while(vectors[i].val<x) i++;
                while(vectors[j].val>x) j--;
                if(!(i>j)){
                         swap(vectors[i],vectors[j]);
                         i++;
                         j--;
                         }
                }while(!i>j);

                if(l<j) sort(l,j,vectors);
                if(i<r) sort(i,r,vectors);
       }

      };

class Graf : public FX
{

public:
        int parents[200003],n,m,value;
        vector vectors[200003];

       Graf(int n,int m)
       {


               for(int i=1;i<=10;i++) parents[i] = i;
               this->n = n;
               this->m = m;
               this->value = 0;
       }

       void Init(int n){

            }
       void Read()
       {
            for(int i=1;i<=m;i++) fin>>vectors[i].x>>vectors[i].y>>vectors[i].val;
       }
       void SortVectors()
       {
            sort(1,m,vectors);
       }

       void ShowVectors()
       {
            for(int i=1;i<=m;i++) cout<<vectors[i].x<<" "<<vectors[i].y<<" "<<vectors[i].val<<endl;
            cout<<endl;
       }

       void ShowParents()
       {
            for(int i=1;i<=n;i++) cout<<parents[i]<<" ";
            cout<<endl;

       }
       void Union(int p, int q)
       {
            int from = parents[p];
            int to = parents[q];
            for(int i=1;i<=n;i++) if(parents[i]==from) parents[i]=to;
            //this->ShowParents();
       }

       bool Connected(int p, int q)
       {
            return parents[p] == parents[q];
       }

       int Apm()
       {
            for(int i=1;i<=m;i++){
                    int p = vectors[i].x;
                    int q = vectors[i].y;
                    //cout<<p<<" "<<q<<" "<<Connected(p,q)<<endl;
                    if(!Connected(p,q)){
                                         Union(p,q);
                                         value += vectors[i].val;
                                         }
                    }
            return value;

       }

      };

int n,i,k,j,m,ac=0,value=0;


int main(){
    fin>>n>>m;
    Graf *graf = new Graf(n,m);
    graf->Read();
    graf->SortVectors();
    fout<<graf->Apm();


}