企业网站建设的策略,程序员培训班要多少钱,wordpress心理教育网站,小程序制作 相册正题
bzoj 3754 题目大意
求最小方差生成树 解题思路
可以枚举数值之和#xff0c;然后跑最小生成树
每次加25#xff0c;这样可以提高速度#xff0c;且如果平均数接近#xff0c;那么所选的边和答案会相同#xff0c;再暴力跑一遍即可 code
#includecmath
…正题
bzoj 3754 题目大意
求最小方差生成树 解题思路
可以枚举数值之和然后跑最小生成树
每次加25这样可以提高速度且如果平均数接近那么所选的边和答案会相同再暴力跑一遍即可 code
#includecmath
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 110
#define M 2021
using namespace std;
int n,m,x,y,mn,mx,top,d[N],fa[N];
double ans;
struct node
{int x,y;double l,L;
}a[M];
int find(int x)
{return fa[x]x?x:fa[x]find(fa[x]);
}
bool cmp(node a,node b)
{return a.lb.l;
}
double min(double a,double b)
{if(ab)return a;return b;
}
double tr()
{double sum0,num0;top0;for(int i1;in;i)fa[i]i;for(int i1;im;i){xfind(a[i].x);yfind(a[i].y);if(xy)continue;fa[x]y;d[top]i;if(topn-1)break;}for(int i1;itop;i)suma[d[i]].L;sum/top;for(int i1;itop;i)num(a[d[i]].L-sum)*(a[d[i]].L-sum);return num;
}
int read()
{char cgetchar();int ds0,fs1;while (c0||c9) {if (x-) fs-1;cgetchar();}while (c0c9) ds(ds3)(ds1)c-48,cgetchar();return ds*fs;
}
int main()
{nread();mread();for(int i1;im;i){a[i].xread();a[i].yread();a[i].la[i].Lread();}ans1000000000;for(int k0;k10000;k25){for(int i1;im;i)a[i].l(a[i].L-1.0*k/(n-1))*(a[i].L-1.0*k/(n-1));sort(a1,a1m,cmp);ansmin(ans,tr());}printf(%.4lf,sqrt(ans/(n-1)));return 0;
}
