Pagini recente » Cod sursa (job #1672632) | Cod sursa (job #1963872) | Cod sursa (job #2366414) | Clasament 23 | Cod sursa (job #1008140)
#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();
}