1<=U,V<=N<=50,N-1<=M<=1000,0<=W<=50。数据不超过5组。
题目分析：要求方差最小，，就是要每条边(val – ave)^2的和最小，枚举所有边权和的可能值，多次kruskal求最小生成树，每次求的时候，以(val – ave)^2作为当前边的权值，如果该树的val和等于我们枚举的和，则修改ans的值，因为题目的数据量很小，复杂度大概为O(NWElogE)大概是1e7左右，基本可以接受
#include <cstdio>#include <algorithm>using namespace std;double const MAX = 10000000000000.0;int n, m, tmp[1005], fa[55];double ans;struct Edge{int u, v;double w, val;}e[1005];bool cmp(Edge a, Edge b){return a.w < b.w;}void UF_set(int n){for(int i = 1; i <= n; i++)fa[i] = i;}int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}void Union(int a, int b){int r1 = Find(a);int r2 = Find(b);if(r1 != r2)fa[r2] = r1;}void Kruskal(int sum){UF_set(n);int cnt = 0;double f_all = 0;double all = 0;double ave = sum * 1.0 / (n – 1);for(int i = 0; i < m; i++)e[i].w = (e[i].val – ave) * (e[i].val – ave);sort(e, e + m, cmp);for(int i = 0; i < m; i++){int u = e[i].u;int v = e[i].v;if(Find(u) != Find(v)){Union(u, v);f_all += e[i].w;all += e[i].val;cnt ++;}if(cnt == n – 1)break;}if((int)all == sum)ans = min(ans, f_all);}int main(){int ca = 1;while(scanf("%d %d", &n, &m) != EOF && (m + n)){// if(n == 1 || n == 2)// {//printf("0.00\n");//continue;// }int minv = 0;int maxv = 0;ans = MAX;for(int i = 0; i < m; i++){scanf("%d %d %lf", &e[i].u, &e[i].v, &e[i].val);tmp[i] = e[i].val;}sort(tmp, tmp + m);for(int i = 0; i < n – 1; i++)minv += tmp[i];for(int i = m – 1; i > m – n; i–)maxv += tmp[i];for(int i = minv; i <= maxv; i++)Kruskal(i);ans = ans / (n – 1);printf("Case %d: %.2f\n", ca++, ans);}}
爬上那座山，听最圣洁的经。
