★★   输入文件：roads.in   输出文件：roads.out   简单对比

时间限制：1 s   内存限制：128 MB

译 by CmYkRgB123

描述

Farmer John 刚刚得到了几个新农场！他想把这几个农场用路连接起来，这样他就可以通过笔直的公路从一个农场到另一个农场了。现在已经有了几条连接着的农场。

N (1 ≤ N ≤ 1,000) 个农场中，每个农场的位置在坐标平面的 (Xi, Yi) (0 ≤ Xi ≤ 1,000,000; 0 ≤ Yi ≤ 1,000,000)。已经有 M (1 ≤ M ≤ 1,000) 条路以前就被建好了。请你帮助 Farmer John 考虑建设尽量少长度的额外的路，使他的农场连在一起。

输入

* 第 1 行: 两个整数: N , M

* 第 2..N+1 行: 两个整数 Xi , Yi

* 第 N+2..N+M+2 行: 两个整数: i , j, 表示已经存在从农场i到农场j的路。

输出

* 第 1 行: 额外的路的最少长度，保留2小数。 请使用 64 位的浮点数。

样例输入

 4 1

 1 1

 3 1

 2 3

 4 3

 1 4

样例输出

 4.00

好久没写最小生成树了结果爆了一堆bug。。

对于已经建造的道路，我们可以把它的权值设置成0

然后跑裸地kruskal

注意内存限制！！！！！！！！！！！

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #define INF 0x7ffff  7 using namespace std;  8 const int MAXN=1001;  9 int vis[MAXN][MAXN];// 记录两个城市之间是否已经有道路相连 10 double dis[MAXN][MAXN];  11 struct node 12 { 13     int u,v,nxt; 14     double w; 15 }edge[1000001]; 16 int f[MAXN*3]; 17 int num=1; 18 struct pos 19 { 20     long long int  x,y; 21 }where[MAXN*3]; 22 int n,m; 23 double ans=0; 24 int read(int & n) 25 { 26     int flag=0,x=0;char c='/'; 27     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;} 28     while(c>='0'&&c<='9')x=x*10+(c-48),c=getchar(); 29     if(flag)n=-x; 30     else n=x; 31 } 32 void deal_dis() 33 { 34     //for(int i=1;i<=n;i++) 35     //    for(int j=1;j
          
           >where[i].x>>where[i].y,f[i]=i; 98 99 for(int i=1;i<=m;i++)100 {101 int x,y;102 read(x);read(y);103 add_edge(x,y,0.00);104 vis[x][y]=1;105 }106 107 deal_dis();108 109 for(int i=1;i<=n;i++)110 for(int j=1;j