Code: Select all
#include<stdio.h>
#include<math.h>
void cloud(int oldvalue,int newvalue,int N);
double distance(int x1,int x2,int y1,int y2);
void heapsort(long int count);
void Build_Max_Heap(long int count);
void Max_Heapify(long int i,long int count);
struct node {
int x;
int y;
int cloud;
int id;
}V[760];
struct edge {
struct node v1;
struct node v2;
double dist;
}E[577600];
int main()
{
int N,i,edge,v1,v2,j,temp,caz;
long int count;
double sum;
while(scanf("%d",&N)==1)
{
for(i=1; i<=N; ++i)
{
scanf("%d %d",&V[i].x,&V[i].y);
V[i].cloud = i;
V[i].id = i;
}
scanf("%d",&edge);
for(i=1; i<=edge; ++i)
{
scanf("%d %d",&v1,&v2);
cloud(v2,v1,N);
}
count = 0;
for(i=1; i<N; ++i)
{
for(j=i+1; j<=N; ++j)
{
if(V[i].cloud != V[j].cloud)
{
count++;
E[count].v1 = V[i];
E[count].v2 = V[j];
E[count].dist = distance(V[i].x,V[j].x,V[i].y,V[j].y);
}
}
}
heapsort(count);
temp = 0;
caz = N - 1 - edge;
j = 1;
sum = 0.0;
while(temp < caz)
{
if(V[E[j].v1.id].cloud != V[E[j].v2.id].cloud)
{
sum += E[j].dist;
cloud(V[E[j].v2.id].cloud,V[E[j].v1.id].cloud,N);
temp++;
}
j++;
}
printf("%.2lf\n",sum);
}
return 0;
}
void cloud(int oldvalue,int newvalue,int N)
{
int i;
for(i=1; i<=N; ++i)
{
if(V[i].cloud == oldvalue)
V[i].cloud = newvalue;
}
}
double distance(int x1,int x2,int y1,int y2)
{
int x,y,dis1;
double dis2;
x = x1-x2;
y = y1-y2;
dis1 = (x*x) + (y*y);
dis2 = dis1*1.0;
return sqrt(dis2);
}
void Build_Max_Heap(long int count)
{
long int i;
for(i=floor(count/2); i>0; --i)
Max_Heapify(i,count);
}
void Max_Heapify(long int i,long int count)
{
long int L,R,largest;
struct edge test;
L = 2*i;
R = 2*i + 1;
if(L<=count && E[L].dist>E[i].dist)
{
largest = L;
}
else
largest = i;
if(R<=count && E[R].dist>E[largest].dist)
largest = R;
if(largest != i)
{
test = E[i];
E[i] = E[largest];
E[largest] = test;
Max_Heapify(largest,count);
}
}
void heapsort(long int count)
{
long int i,c;
struct edge test;
c = count;
Build_Max_Heap(count);
for(i=c; i>1; --i)
{
test = E[i];
E[i] = E[1];
E[1] = test;
c--;
Max_Heapify(1,c);
}
}