考虑对于$n-1$个数$a_{i}$，函数$f(x)=frac{sum_{i=1}^{n-1}(x-a_{i})^{2}}{n-1}$的最小值恰在$x=frac{sum_{i=1}^{n-1}a_{i}}{n-1}$取到（根据二次函数显然），因此题意可以理解为任选实数$b$并最小化$frac{sum_{i=1}^{n-1}(b-a_{i})^{2}}{n-1}$（本来要求$b$为平均值）
可以暴力枚举$b$并将边权从$d$变为$(b-d)^{2}$求最小生成树，但由于$b$为实数，并不能直接枚举
（为了方便，以下约定两条边边权若相同，编号小的更小）
对于最小生成树而言，所选的边事实上仅取决于边的大小关系，考虑两条边$i$和$j$（其中$i<j$）满足$i$在$j$前面当且仅当$Xle lfloorfrac{w_{i}+w_{j}}{2} floor$，以此法即产生了$o(n^{4})$个区间，每一个区间内大小关系都相同
（每一段都是左端点为圆括号，右端点为中括号）
对于每一段，以$b$作为参数来表示边权，比较时使用区间内任意数字即可，最后即求一个二次函数区间（其实也可以忽略区间限制）最小值，即可做到$o(n^{6})$的复杂度，可以通过
（以下可能有一些口胡）
更进一步的，考虑每一次权值变化即将两条边优先级交换，且交换的两边优先级相邻（不妨假设为两边为$i$和$j$，其中交换前$i$优先级较大），此时不难证明——
如果修改最小生成树，则必然是$i$本来在最小生成树中被删除，$j$本来不在最小生成树中被加入（其余边不修改）
（证明考虑kruskal贪心的过程并分类讨论即可）
因此只需要判定能否替换即可，用按秩合并并查集维护，复杂度为$o(n^{4}log n)$
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 25 4 #define sqr(k) (k)*(k) 5 struct fun{ 6 double a,b,c,val; 7 fun(){ 8 a=b=c=val=0; 9 } 10 fun(double aa,double bb,double cc,double vall){ 11 a=aa,b=bb,c=cc,val=vall; 12 } 13 bool operator < (const fun &k)const{ 14 return val<k.val; 15 } 16 fun operator + (const fun &k)const{ 17 return fun(a+k.a,b+k.b,c+k.c,0); 18 } 19 double mn(){ 20 return c-sqr(b)/(4*a); 21 } 22 }D[N],w[N][N]; 23 vector<double>v; 24 int n,vis[N]; 25 double ans,d[N][N]; 26 fun calc(){ 27 fun ans; 28 D[0]=fun(); 29 for(int i=1;i<n;i++)D[i]=fun(0,0,0,1e15); 30 memset(vis,0,sizeof(vis)); 31 for(int i=0;i<n;i++){ 32 int k=-1; 33 for(int j=0;j<n;j++) 34 if ((!vis[j])&&((k<0)||(D[j]<D[k])))k=j; 35 vis[k]=1; 36 ans=ans+D[k]; 37 for(int j=0;j<n;j++)D[j]=min(D[j],w[k][j]); 38 } 39 return ans; 40 } 41 class Egalitarianism2{ 42 public: 43 double minStdev(vector<int>x,vector<int>y){ 44 n=x.size(); 45 for(int i=0;i<n;i++) 46 for(int j=0;j<n;j++)d[i][j]=sqrt(1LL*sqr(x[i]-x[j])+1LL*sqr(y[i]-y[j])); 47 for(int i=0;i<n;i++) 48 for(int j=i+1;j<n;j++) 49 for(int ii=i;ii<n;ii++) 50 for(int jj=ii+1;jj<n;jj++) 51 if ((i<ii)||(j<jj))v.push_back((d[i][j]+d[ii][jj])/2); 52 sort(v.begin(),v.end()); 53 double lst=0; 54 ans=1e15; 55 for(int i=0;i<v.size();i++) 56 if ((!i)||(v[i]!=v[i-1])){ 57 for(int j=0;j<n;j++) 58 for(int k=0;k<n;k++)w[j][k]=fun(1,-2*d[j][k],sqr(d[j][k]),sqr(v[i]-d[j][k])); 59 ans=min(ans,calc().mn()/(n-1)); 60 lst=v[i]; 61 } 62 return sqrt(ans); 63 } 64 };