Description

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 (X_i,Y_i) on the plane (0 ≤X_i ≤ 1,000,000; 0 ≤Y_i ≤ 1,000,000). Given the preexistingM 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.

Input

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Two space-separated integers: X_i andY_i

* Lines N+2..N+M+2: Two space-separated integers: i and j, indicating that there is already a road connecting the farmi and farmj.

Output

* 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.

Sample Input

4 11 13 12 34 31 4

Sample Output

4.00

 

 

坐标类的最短路；

基础题。同时再总结一下Prim算法。

选取一个根节点，每次选取与树距离最短的一条路加入。

此题利用邻接矩阵。

 

在这总结一下最短路Prim与Kruskal的区别：

Prim适合于邻接矩阵，而Kruskal更适合于邻接表。

同时得出一个结论，Prim算法比较适合求稠密图的最小生成树，Kruskal算法比较适合求稀疏图的最小生成树。

 

在做题时要注意如何选择Prim与Kruskal。

当点少边多时，如1000个点500000条边时，这种变态数据，Prim就要开1000*1000的数组；

而Kruskal只需开一个500000数组。

当点多边少时如500000个点，1000条边，这主要是为了限制内存。Prim就绝对没戏，Kruskal就笑了。

同时，在满足空间的情况下，一般数据的Prim的时间是能完全碾压Kruskal的，大概在20倍左右。此时会有，在变态空间数据选择Kruskal时会超时，而Prim优化内存这不能搞，这时就得Kruskal优化时间了。即在普通Kruskal搜索选择最小边时，做文章，由于每次都得重复搜素最小边，不如一开始将其排序，改进后变为Kruskal+qsort，这时时间就能与Prim相差无几。事实上我们用kruskal一般都是先排序的。所以空间大的时候，和其他情况都可以用到kruskal。

 

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn=1002;const double maxm=2000000;bool visit[maxn];int n;double sum;double x[maxn],y[maxn],lowcost[maxn],weight[maxn][maxn];double dist(double x1,double y1,double x2,double y2){    return sqrt(pow(x2-x1,2)+pow(y2-y1,2));}void Prim(int u){    int i,j,k;    double min;    for(i=1;i<=n;i++)    if(i!=u)    lowcost[i]=weight[1][i];    //lowcost取1节点到其他节点的距离。        visit[1]=true;      for(i=1;i
        
         weight[k][j] && !visit[j])//能是lowcost始终为树外最小的n条路。        lowcost[j]=weight[k][j];    }}int main(){    int i,j,m,a,b;    while(scanf("%d%d",&n,&m)!=EOF)    {        for(i=1;i<=n;i++)      //农场从1开始标号        scanf("%lf%lf",&x[i],&y[i]);        for(i=1;i<=n;i++)        for(j=1;j<=n;j++)        weight[i][j]=maxm;        for(i=1;i