TXT

uva10397 connect the campus

By Connie Hunt,2014-11-07 00:39
13 views 0
uva10397 connect the campus

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

#include<cstring> using namespace std; struct Edge{

int x,y;

double w;//?ÈµÄÆ??? }map[300000];

const int maxn = 760; int father[maxn]; int point[maxn][2]; int t,n,cas,ans; double sum;

bool cmp(Edge a,Edge b){

return a.w<b.w; }

void Initial(){

sum = 0;

ans = 0;

memset(point,0,sizeof(point));

for(int i = 1; i <= t; i++){

father[i] = i;

}

}

int Find(int x){

if(father[x] == x){

return x;

}

return (father[x]=Find(father[x]));

}

int Union(int x,int y){

int a = Find(x);

int b = Find(y);

if(a != b){

father[a] = b;

return 1;

}

return 0;

}

void Unio(int x,int y){

int a = Find(x);

int b = Find(y);

if(a != b){

father[a] = b;

}

}

void Input(){

for(int i = 1; i <= t; i++){

cin >> point[i][0] >> point[i][1];

//cout << point[i][0] << " " << point[i][1] << endl;

}

int con,x,y;

cin >> con;

for(int i = 1; i <= con; i++){

cin >> x >> y;

Unio(x,y);

}

for(int i = 1; i < t; i++){

for(int j = i+1; j <= t;j++){

ans++;

map[ans].w =

(point[i][0]-point[j][0])*(point[i][0]-point[j][0])+(point[i][1]-p

oint[j][1])*(point[i][1]-point[j][1]);

map[ans].x = i;

map[ans].y = j;

}

}

/*cout<<"map"<<endl;

for(int j = 1; j <= ans; j++){

cout << map[j].x <<" " << map[j].y << " " << map[j].w << endl;

}cout<<"map"<<endl;*/

}

void Computing(){

for(int i = 1; i <= ans; i++){

int a = Union(map[i].x,map[i].y);

if(a){

sum += sqrt(map[i].w);

}

}

}

void Output(){

printf("%.2f\n",sum);

}

int main(){

cas = 0;

while(cin>>t){

Initial();

Input();

sort(map+1,map+ans+1,cmp);

Computing();

Output();

}

system("pause");

return 0;

}

Report this document

For any questions or suggestions please email
cust-service@docsford.com