aoj2224:Save_your_cats.cpp

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
struct edge{
    int u,v;
    double cost;
    edge(int a,int b,double c):u(a),v(b),cost(c){}
    edge(){}
    bool operator<(const edge &d)const{
        return cost<d.cost;
    }
};
int uf_par[10000],uf_rank[10000];
void uf_init(int n){
    for(int i=0;i<n;i++){
        uf_par[i]=i;
        uf_rank[i]=0;
    }
}
int uf_find(int x){
    return (uf_par[x]==x)?(x):(uf_par[x]=uf_find(uf_par[x]));
}
void uf_unite(int x,int y){
    x=uf_find(x);
    y=uf_find(y);
    if(x==y)return;
 
    if(uf_rank[x]<uf_rank[y])uf_par[y]=x;
    else{
        uf_par[x]=y;
        if(uf_rank[x]==uf_rank[y])uf_rank[x]++;
    }
}
bool uf_same(int x,int y){
    return uf_find(x)==uf_find(y);
}
int main(){
    int x[10000],y[10000];
    int n,m;
    vector<edge>es;
    double sum=0.0,res=0.0;
    cin>>n>>m;
    uf_init(n);
    es.resize(m);
    for(int i=0;i<n;i++)cin>>x[i]>>y[i];
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        double dis=sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
        es[i]=edge(a,b,-dis);
        sum+=dis;
    }
    sort(es.begin(),es.end());
    for(int i=0;i<m;i++){
        edge e=es[i];
        if(uf_same(e.u,e.v))continue;
        uf_unite(e.u,e.v);
        res+=e.cost;
    };
    cout<<fixed<<sum+res<<endl;
 
    return 0;
}