动态型网站建设哪里便宜,宁夏网站建设报价,江门平台入口,深圳阿里网站设计公司正题 题目大意
在一张图中选择一颗生成树使得边权的方差最小。 解题思路
我们很容易想到一种贪心#xff0c;那就是在按照边权排好序后选择一段连续的区间然后使用这段区间构成最小生成树#xff0c;这样时间复杂度是O(m3logm)O(m^3\log m)O(m3logm)#xff0c;时间复杂…正题 题目大意
在一张图中选择一颗生成树使得边权的方差最小。 解题思路
我们很容易想到一种贪心那就是在按照边权排好序后选择一段连续的区间然后使用这段区间构成最小生成树这样时间复杂度是O(m3logm)O(m^3\log m)O(m3logm)时间复杂度难以接受。
那我们可以考虑枚举一个数xxx(精度在0.10.10.1内即可)然后将边权按照∣w−x∣|w-x|∣w−x∣排序然后优先选取。每次枚举取最小值。
时间复杂度O(1000∗mlogm)O(1000*m\log m)O(1000∗mlogm)可以通过本题。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includecmath
using namespace std;
const int N2110;
struct node{int x,y;double w,c;bool ok;
}a[N];
int n,m,fa[N];
double ans;
bool cMp(node x,node y)
{return x.wy.w;}
int find(int x)
{return fa[x]x?x:fa[x]find(fa[x]);}
double check(double k)
{for(int i1;in;i)fa[i]i;for(int i1;im;i)a[i].wfabs(a[i].c-k),a[i].ok0;sort(a1,a1m,cMp);double ave0,ans0;for(int i1;im;i)if(find(a[i].x)!find(a[i].y))fa[fa[a[i].x]]fa[a[i].y],avea[i].c,a[i].ok1;ave/1.0*(n-1);for(int i1;im;i)if(a[i].ok) ans(a[i].c-ave)*(a[i].c-ave);return sqrt(ans/(1.0*(n-1)));
}
int main()
{scanf(%d%d,n,m);for(int i1;im;i)scanf(%d%d%lf,a[i].x,a[i].y,a[i].c);ans2147483647;for(double i0;i100;i0.1)ansmin(ans,check(i));printf(%.4lf,ans);
}
