qwq

跑最小生成树

一共n个电话，所以相当于最小生成树里删去最大的n-1的边

所以答案即为最小生成树的第n大边

prim或者kruskal都行

这是prim

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 int x[505], y[505]; 7 int p, n, now, cnt; 8 double ans[505], dis[505][505], d[505]; 9 bool used[505];10 bool cmp(double a,double b){11      return a>b;12 }13 int main(){14     scanf("%d%d",&p,&n);15     for(int i=1; i<=n; i++){16         scanf("%d%d",&x[i],&y[i]);17         d[i]=0x3f3f3f3f;18     }19     for(int i=1; i<=n; i++){20         for(int j=1; j
         
          d[j] && !used[j]){34                 minn=d[j];35                 now=j;36             }37         }38         used[now]=true;39         ans[++cnt]=minn;40         for(int j=1; j<=n; j++){41             if(!used[j]){42                 d[j]=min(d[j], dis[now][j]);43             }44         }45     }46     sort(ans+1, ans+n+1, cmp);//按照从大到小排序47     printf("%.2lf", ans[p]);48     return 0;49 }
         
        
       
      
     

这是kruskal，来自于pushinl

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #define N 501 7 using namespace std; 8 int f[N], px[N], py[N]; 9 double ans[N];10 int n, k, num, cnt;11 struct data{12     int x, y;13     double d;14 }b[N*N];15 double dis(int ax, int ay, int bx, int by){16     return sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));17 }18 int find(int x){19     if(f[x]!=x)f[x]=find(f[x]);20     return f[x];21 }22 inline bool cmp(const data&a, const data&b){23     return a.d
         
        
       
      
     

话说luogu数据真的是十分水了orzzz