这道题是最小生成树树的变形。题目告诉你在其中已经添加过了一些边，在剩下的边中选取若干条使其成为一个最小生成树。

我记得上一次做真题是遇到类似的问题。我用了prime算法求解。现在就换用了kruskal算法。

根据查询选把相应边合并，这些边不算入虽小生成树的权值即可，接下来的就和kruskal算法一致。

代码如下：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #define INF 0x7fffffff 8 #define LEN 1010 9 using namespace std;10 11 typedef struct{12 double x, y;13 }POINT;14 15 typedef struct {16 int a, b;17 double v;18 }ARC;19 20 int n, m, top, parent[LEN];21 POINT p[LEN];22 ARC Arc[LEN*LEN];23 double Map[LEN][LEN];24 25 inline double dis(POINT a, POINT b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}26 bool cmp(ARC a, ARC b){ return a.v