题目大意：求一个图的最小标准差生成树。
思路：毫无思路，之后看了题解。居然是一个很厉害的暴力。
一个很关键的地方：枚举平均值，然后根据(a – ave(a))^2将边排序，做最小生成树。所有的标准差最小值就是答案。
但是这是为什么？如果当前枚举的ave(a)并不是选取的边的平均值怎么办？
那么就一定有一个你会枚举到的ave(a)计算之后的标准差要比现在小。
这样基本就可以说明这个做法的正确性了。但是需要枚举的范围很大，，虽然c只有100，但是按照多大枚举呢。很显然是按照EPS = 1.0 / (m – 1)枚举，因为平均值一定在这其中产生。还有一个小剪枝就是将原图做一次最小生成树和最大生成树，确定枚举的上界和下界。
（为什么我的代码跑了10s+555~~~
CODE：#include <cmath>#include <cstdio>#include <cstring>#include <iomanip>#include <iostream>#include <algorithm>#define MAX 2010#define INF 0x3f3f3f3f#define EPS (1.0 / (points – 1))using namespace std;struct Edge{int x,y,len;double temp;bool operator <(const Edge &a)const {return len < a.len;}void Read() {scanf("%d%d%d",&x,&y,&len);}}edge[MAX];int points,edges;int father[MAX];int Find(int x){if(father[x] == x)return x;return father[x] = Find(father[x]);}inline int MST(){for(int i = 1; i <= points; ++i)father[i] = i;int re = 0;for(int i = 1; i <= edges; ++i) {int fx = Find(edge[i].x);int fy = Find(edge[i].y);if(fx != fy) {father[fx] = fy;re += edge[i].len;}}return re;}bool cmp(const Edge &a,const Edge &b){return a.temp < b.temp;}inline double Calc(double average){for(int i = 1; i <= points; ++i)father[i] = i;for(int i = 1; i <= edges; ++i)edge[i].temp = (average – edge[i].len) * (average – edge[i].len);sort(edge + 1,edge + edges + 1,cmp);double re = .0;for(int i = 1; i <= edges; ++i) {int fx = Find(edge[i].x);int fy = Find(edge[i].y);if(fx != fy) {father[fx] = fy;re += edge[i].temp;}}return sqrt(re / (points – 1));}int main(){cin >> points >> edges;for(int i = 1; i <= edges; ++i)edge[i].Read();sort(edge + 1,edge + edges + 1);double range_min = (double)MST() / (points – 1);reverse(edge + 1,edge + edges + 1);double range_max = (double)MST() / (points – 1);double ans = INF;for(int i = 0; EPS * i + range_min <= range_max; ++i)ans = min(ans,Calc(EPS * i + range_min));cout << fixed << setprecision(4) << ans << endl;return 0;}
当眼泪流尽的时候，留下的应该是坚强。
