网站安全性怎么做,能免费做片头的网站,网站建设与管理专业的行业发展,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;
}
