Uva 10397 - Connect the Campus

题目来源：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=116&problem=1338&mosmsg=Submission+received+with+ID+8905555

题目大意：见代码
题目分析：见代码

//Uva  10397 - Connect the Campus
//给定一些点及一些边，通过添加最少长度的线段使之所有点均连通
//并查集的应用
//先求出各连通分量
//再求出各个连通分量距其它连通分量的最短距离
//再求缩点后的最小生成树
#include <iostream>
#include <cmath>
#include <vector>
#include <iomanip>
#include <algorithm>
#define INF 200000000.0
using namespace std;
const int maxn=800;
struct point
{
    double x;
    double y;
    point(double a=0.0,double b=0.0):x(a),y(b){}
}p[maxn];
struct node
{
    int v1;
    int v2;
    double d;
    node(int a=0,int b=0,double c=0.0):v1(a),v2(b),d(c){}
};
bool cmp(node a,node b)
{
    return a.d<b.d;
}
double dis(point p1,point p2)
{
    double x=p2.x-p1.x;
    double y=p2.y-p1.y;
    return sqrt(x*x+y*y);
}
int n;//顶点数量
int father[maxn],rank[maxn];//用于并查集
vector<vector<int> > v;//存储每一个连通分量的顶点
vector<node> d;//存储任意两个连通分量间的最短距离
//并查集部分
void make_set(int x)
{
    father[x]=x;
    rank[x]=1;
}
int find(int x)
{
    if(x!=father[x])     father[x]=find(father[x]);
    return father[x];
}
int Union(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)    return 0;
    if(rank[x]<rank[y])     father[x]=y;
    else    if(rank[x]==rank[y])    {father[x]=y;rank[y]++;}
    else    father[y]=x;
    return 1;
}
double cal(int a,int b)
{
    double minv=INF;
    int len1=v[a].size();
    int len2=v[b].size();
    for(int i=0;i<len1;i++)
    {
        for(int j=0;j<len2;j++)
        {
            minv=min(minv,dis(p[v[a][i]],p[v[b][j]]));
        }
    }
    return minv;
}
int main()
{
    while(cin>>n)
    {
        for(int i=1;i<=n;i++)
        {
            cin>>p[i].x>>p[i].y;
            make_set(i);
        }
        int m,a,b;
        cin>>m;
        for(int i=0;i<m;i++)
        {
            cin>>a>>b;
            Union(a,b);
        }
        v.assign(n+1,vector<int>());
        int e=0;
        for(int i=1;i<=n;i++)
        {
            int x=find(i);
            if(v[x].size()==0)  e++;
            v[x].push_back(i);
        }
        d.clear();
        for(int i=1;i<=n;i++)
        {
            if(v[i].size()==0)  continue;
            for(int j=i+1;j<=n;j++)
            {
                if(v[j].size()==0)  continue;
                double r=cal(i,j);
                d.push_back(node(i,j,r));
            }
        }
        sort(d.begin(),d.end(),cmp);
        double sum=0.0;
        for(int i=1;i<=n;i++)
        {
            make_set(i);
        }
        for(int i=0;i<d.size();i++)
        {
            node r=d[i];
            if(Union(r.v1,r.v2))    sum+=d[i].d;
        }
        cout<<fixed<<setprecision(2)<<sum<<endl;
    }
    return 0;
}