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;
}