一、思路

　　枚举所有生成树的边权和值，对每一个枚举的边权和值$sum$，修改所有边的边权为$(\frac{es[i].cost - sum}{N - 1})^2$，即方差公式的分子，然后跑最小生成树算法，同时记录边的原来的权值和，如果求出的“最小方差”生成树的边权值和为sum，那么，用这个"最小方差"去更新答案。

二、复杂度分析

　　时间复杂度：O(N * W * M * logM)。N * W为枚举边权和值的时间。边权和值最小为0，最大为(N - 1) * W。

三、PS

　　这题据说蓝桥杯官网数据有问题。有5个样例(2、3、4、5、6)，总是WA。所以，正确的代码也只能得50分。

四、源代码

#include
     
      using namespace std;int N, M;const int MAXN = 55, MAXM = 1010;const double INF = (1LL << 60) * 1.0;typedef struct Edge0 {    int u, v, oldcost;    double newcost;    bool operator < (Edge0 e) const {        return newcost < e.newcost;    }    void assgin(int _u, int _v, int _cost) {        u = _u;        v = _v;        oldcost = _cost;    }} Edge;Edge edges[MAXM];template 
      
        inline void read(T &x) {    int t;    bool flag = false;    while((t = getchar()) != '-' && (t < '0' || t > '9')) ;    if(t == '-') flag = true, t = getchar();    x = t - '0';    while((t = getchar()) >= '0' && t <= '9') x = x * 10 + t - '0';    if(flag) x = -x;}/**并查集部分*/int par[MAXN], rank[MAXN];void init_ufind() {    for(int i = 0; i < MAXN; ++i) {        par[i] = i;        rank[i] = 0;    }}int ufind(int x) {    return x == par[x] ? x : par[x] = ufind(par[x]);}void unite(int x, int y) {    x = ufind(x), y = ufind(y);    if(x == y)return;    if(rank[x] < rank[y])par[x] = y;    else {        par[y] = x;        if(rank[x] == rank[y])rank[x]++;    }}bool same(int x, int y) {    return ufind(x) == ufind(y);}/**并查集部分*/double kruscal(int tot) {    double avg = tot * 1.0 / (N - 1);    for(int i = 0; i < M; ++i) {        edges[i].newcost = (edges[i].oldcost * 1.0 - avg) * (edges[i].oldcost * 1.0 - avg);    }    sort(edges, edges + M);    init_ufind();    double res = 0;    int ires = 0;    for(int i = 0; i < M; ++i) {        Edge& e = edges[i];        if(!same(e.u, e.v)) {            unite(e.u, e.v);            res += e.newcost;            ires += e.oldcost;        }    }    if(ires == tot)return res / (N - 1);    else return INF;}int main() {#ifndef ONLINE_JUDGE    freopen("input.txt", "r", stdin);#endif    int T = 1, a, b, c;    int costs[MAXM];    while(scanf("%d%d", &N, &M), !(N == 0 && M == 0)) {        for(int i = 0; i < M; ++i) {            read(a), read(b), read(c);            edges[i].u = a, edges[i].v = b, edges[i].oldcost = c;            costs[i] = c;        }        sort(costs, costs + M);        int mintot = 0, maxtot = 0;        for(int i = 0;i < N - 1;++i)mintot += costs[i];        for(int i = M - 1;i > M - N;--i)maxtot += costs[i];        double ans = INF;        for(int tot = mintot; tot <= maxtot; ++tot) {            ans = min(ans, kruscal(tot));        }        printf("Case %d: %.2f\n", T++, ans);    }    return 0;}