## 10397 - Connect the Campus

Moderator: Board moderators

Zin_tas
New poster
Posts: 3
Joined: Mon Feb 09, 2015 11:05 pm

### Re: 10397 - Connect the Campus

I don't know why I'm getting wa... can anybody plz help me???? ive tried all d sample inputs given here...

Code: Select all

``````#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>

using namespace std;

class Building{

public:

int x,y,serial;
Building *parent;

Building(int bx,int by, int s){
x=bx;
y=by;
serial=s;
parent=NULL;
//reprsentitive=this;
}

void set_parent(Building a){
this->parent=a.find_root();
}

Building* find_root(){

if (!this->parent) return this;
else{
this->parent=this->parent->find_root();
return this->parent;
}
}

};

class Edges{

public:
int v1,v2;
int flag;
double distance;
Edges(Building a, Building b){

v1=a.serial;
v2=b.serial;
flag=0;
distance=pow(pow(a.x-b.x,2.0)+pow(a.y-b.y,2.0),0.5);
}

bool operator <(const Edges& r){ return this->distance<r.distance; }
};

int main (void){

int N,M,x,y,i,j,k;
double dis;
vector<Building> B;
vector<Edges> E;
vector<Edges> MST;
//while(cin>>N)
while(scanf("%d",&N)==1){

dis=0;

for(i=0;i<N;i++){
cin>>x>>y;
B.push_back(Building(x,y,i+1));
}

for(i=0;i<N;i++){
for(j=i+1;j<N;j++){
E.push_back(Edges(B[i],B[j]));
}
}

sort(E.begin(),E.end());

cin>>M;
for(i=0;i<M;i++){

cin>>x>>y;
if(y<x) swap(x,y);
for(size_t j=0;j<E.size();j++){
if(E[j].v1== x && E[j].v2==y){
MST.push_back(E[j]);
E[j].flag=1;
break;
}
}

B[y-1].parent=B[x-1].find_root();

}

for(size_t j=0;j<E.size();j++){
//if(i==N-1) break;
if(E[j].flag!=1){
Building *u,*v;
u=B[E[j].v1-1].find_root();
v=B[E[j].v2-1].find_root();
if(u==v) continue;
else{
v->parent=u;
//v->parent->find_root()=u->find_root();

//B[E[j].v2-1].parent=B[E[j].v1-1].find_root();
MST.push_back(E[j]);
E[j].flag=1;
i++;
}

}
}

//for(size_t i=0;i<B.size();i++) cout<<B[i].serial<<"	"<<B[i].x<<"   "<<B[i].y<<"		"<<B[i].parent<<endl;
//for(size_t i=0;i<E.size();i++) cout<<E[i].v1<<"	"<<E[i].v2<<"   "<<E[i].distance<<"jhj"<<endl;
//for(size_t i=0;i<MST.size();i++) cout<<MST[i].v1<<"	"<<MST[i].v2<<"   "<<MST[i].distance<<endl;
for(size_t i=M;i<MST.size();i++) dis+=MST[i].distance;
//cout.precision(2);
//cout.width(4);
//cout<<"				"<<dis;
printf("%.2lf\n",dis);
E.clear();
B.clear();
MST.clear();
}
return 0;
}``````
Last edited by brianfry713 on Wed Apr 08, 2015 11:41 pm, edited 1 time in total.