P2872 [USACO07DEC]道路建设Building Roads
kruskal求最小生成树。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#define re register
using namespace std;
typedef double ld;
typedef long long ll;
ll sqr(ll a){return a*a;}
#define N 1002
struct node{ll x,y;}a[N];
struct edge{
int f,t; ld dis;
edge(){}
edge(int A,int B,ld C):
f(A),t(B),dis(C)
{}
bool operator < (const edge &tmp) const{return dis<tmp.dis;}
}b[N*N];
int n,m,tp,fa[N],k; ld ans;
ld dist(node A,node B){return sqrt((ld)(sqr(A.x-B.x)+sqr(A.y-B.y)));}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void uni(int x,int y){
int r1=find(x),r2=find(y);
if(r1!=r2) fa[r2]=r1;
}
int main(){
scanf("%d%d",&n,&m); int q1,q2;
for(re int i=;i<=n;++i){
scanf("%lld%lld",&a[i].x,&a[i].y); fa[i]=i;
for(re int j=;j<i;++j) b[++tp]=edge(j,i,dist(a[j],a[i]));//把可能的边存起来
}sort(b+,b+tp+);
for(re int i=;i<=m;++i){
scanf("%d%d",&q1,&q2);
if(find(q1)!=find(q2)) ++k,uni(q1,q2);
}
for(re int i=;i<=tp&&k<n-;++i)
if(find(b[i].f)!=find(b[i].t)){
uni(b[i].f,b[i].t);
ans+=b[i].dis; ++k;
}
printf("%.2lf",ans);
return ;
}