TXT

uva10397 connect the campus

By Connie Hunt,2014-11-07 00:39
10 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