Page 6 of 6

Re: 10397 - Connect the Campus

Posted: Mon Apr 06, 2015 4:39 pm
by Zin_tas
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;
}