记得在哪里做过一遍，最简单的最小生成树，直接用kruskal秒掉了。

代码如下：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #define LEN 110 8 using namespace std; 9 10 typedef struct {11 double x, y;12 }POINT;13 14 POINT Point[LEN];15 16 typedef struct {17 int a, b;18 double w;19 }ARC;20 21 ARC Arc[LEN*LEN];22 int top, n;23 24 inline double dis(POINT a, POINT b){25 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));26 }27 28 //UFSet29 int parent[LEN];30 31 void init(){32 for(int i=0; i