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.
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Two space-separated integers: Xi and Yi
* Lines N+2..N+M+2: Two space-separated integers: i and j, indicating that there is already a road connecting the farm i and farm j.
* Line 1: Smallest length of additional roads required to connect all farms, printed without rounding to two decimal places. Be sure to calculate distances as 64-bit floating point numbers.
4 1 1 1 3 1 2 3 4 3 1 4
4.00
很明显的最小生成树，可以说是让我最无语的题目之一了，比赛没A是因为坐标没设成double而是int
代码：
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<queue>
#include<cstring>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;
#define M 102
struct node{double x,y;
}a[1005];
struct edge{int s,e;double v;bool operator <(const edge& obj)const{return v<obj.v;}
}p[1000100];
int n,m;
int fat[1005];
int father(int x)
{if(fat[x]!=x) fat[x]=father(fat[x]);return fat[x];
}
void unionn(int x,int y)
{int fa=father(x);int fb=father(y);if(fa!=fb) fat[fa]=fb;
}
int main()
{int fa,fb,i,j,t1,t2,tot,num;double dis;scanf("%d%d",&n,&m);for(i=1;i<=n;i++){scanf("%lf%lf",&a[i].x,&a[i].y);}num=0;for(i=1;i<=n;i++)for(j=i+1;j<=n;j++){dis=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));p[num].s=i; p[num].e=j; p[num].v=dis; num++;//p[num].s=j; p[num].e=i; p[num].v=dis; num++;}for(i=1;i<=n;i++) fat[i]=i;tot=0;for(i=1;i<=m;i++){scanf("%d%d",&t1,&t2);fa=father(t1);fb=father(t2);if(fa!=fb) {fat[fa]=fb;tot++;} //之前给的路径中可以在最小生成树中可以生成一条边tot++}sort(p,p+num);double cnt=0;for(i=0;i<num;i++){if(father(p[i].s)!=father(p[i].e)){unionn(p[i].s,p[i].e);cnt+=p[i].v;tot++;}if(tot==(n-1)) break;}//cnt+=0.005;cout<<fixed<<setprecision(2)<<cnt<<endl;return 0;
}