Farmer John had just acquired several new farms! He wants to connect the farms with roads so that he can travel from any farm to any other farm via a sequence of roads; roads already connect some of the farms.
Each of the N (1 ≤ N ≤ 1,000) farms (conveniently numbered 1..N) is represented by a position (Xi, Yi) on the plane (0 ≤ Xi ≤ 1,000,000; 0 ≤ Yi ≤ 1,000,000). Given the preexisting M roads (1 ≤ M ≤ 1,000) as pairs of connected farms, help Farmer John determine the smallest length of additional roads he must build to connect all his farms.
给出nn个点的坐标,其中一些点已经连通,现在要把所有点连通,求修路的最小长度.
输入格式：
Line 1: Two space-separated integers: N and M
Lines 2..N+1: Two space-separated integers: Xi and Yi
输出格式：
4 1 1 1 3 1 2 3 4 3 1 4
4.00
最小生成树裸题
#include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 510000 using namespace std; int n,m,x,y,s,fx,fy,xx[N],yy[N],fa[N]; int read() { int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();} return x*f; } struct Edge { int x,y; double z; }edge[N<<1]; int cmp(Edge a,Edge b) { return a.z<b.z; } int find(int x) { if(fa[x]==x) return x; fa[x]=find(fa[x]); return fa[x]; } int main() { n=read(),m=read(); for(int i=1;i<=n;i++) xx[i]=read(),yy[i]=read(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j) { ++s; edge[s].x=i; edge[s].y=j; edge[s].z=sqrt(pow(xx[i]-xx[j],2)+pow(yy[i]-yy[j],2)); } for(int i=1;i<=n;i++) fa[i]=i; double ans=0; for(int i=1;i<=m;i++) { x=read(),y=read(); fx=find(x),fy=find(y); fa[fx]=fy; } sort(edge+1,edge+1+s,cmp); for(int i=1;i<=s;i++) { x=edge[i].x,y=edge[i].y; fx=find(x),fy=find(y); if(fa[fx]==fy) continue; fa[fx]=fy; ans+=edge[i].z; } printf("%.2lf",ans); return 0; }
洛谷——P2872 [USACO07DEC]道路建设Building Roads
原文：http://www.cnblogs.com/z360/p/7468764.html