1 /* 2     The first line of each test case contains 1 <= S <= 100, the number of satellite channels! 3     注意：S表示一共有多少个卫星，那么就是有 最多有S-1个通道！ 然后将最小生成树中的后边的 S-1通道去掉就行了！  4     思路：最小生成树中的第 k 个最小边！  5 */ 6 //克鲁斯克尔算法..... 7 #include
     
       8 #include
      
        9 #include
       
        10 #include
        
         11 #include
         
          12 using namespace std;13 14 double x[800], y[800];15 16 struct node{17    int u, v; 18    double d;19 };20 21 bool cmp(node a, node b){22     return a.d < b.d;23 }24 25 int f[505];26 27 node nd[150000];28 double ret[505];29 30 int getFather(int x){31    return x==f[x] ? x : f[x]=getFather(f[x]);32 }33 34 bool Union(int a, int b){35    int fa=getFather(a), fb=getFather(b);36    if(fa!=fb){37        f[fa]=fb;38        return true;39    }40    return false;41 }42 43 int main(){44    int n, m;45    int t;46    scanf("%d", &t);47    while(t--){48           scanf("%d%d", &m, &n);49        for(int i=1; i<=n; ++i){50           scanf("%lf%lf", &x[i], &y[i]);51           f[i]=i;52        }53        int cnt=0;54        for(int i=1; i
         
        
       
      
     

1 //prim算法....... 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 using namespace std; 8 const double INF = 0x3f3f3f3f*1.0; 9 double x[800], y[800];10 11 int n, m;12 double map[505][505];13 int vis[505];14 15 double ret[505];16 17 void prim(){18     memset(vis, 0, sizeof(vis));19     vis[1]=1;20     for(int i=2; i<=n; ++i)21        ret[i]=INF;22     int root=1, p;23     for(int i=1; i
           
            map[root][j])27 ret[j]=map[root][j];28 if(!vis[j] && minLen>ret[j]){29 minLen=ret[j];30 p=j; 31 }32 }33 root=p;34 vis[root]=1;35 }36 }37 38 int main(){39 40 int t;41 scanf("%d", &t);42 while(t--){43 scanf("%d%d", &m, &n);44 for(int i=1; i<=n; ++i)45 scanf("%lf%lf", &x[i], &y[i]);46 for(int i=1; i