蓝桥杯练习题 最小方差生成树 (Kruskal MST 好题)

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 <cstring>
#include <algorithm>
using namespace std;
double const MAX = 10000000000000.0;
int fa[55], map[55][55];
int minv, maxv;
int n, m, cnt, a[55];
double ans;

struct Edge
{
    int u, v, w;
    double fw;
}e[55];

bool cmp(Edge a, Edge b)
{
    return a.fw < b.fw;
}

bool cmp1(int a, int b)
{
    return a > b;
}

void UF_set()
{
    for(int i = 0; i < 55; i++)
        fa[i] = i;
}

int Find(int x)
{
    return x == fa[x] ? x : fa[x] = Find(fa[x]);
}

int 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();
    double fall = 0;
    cnt = 0;
    int all = 0;
    double ave = (sum * 1.0) / ((n - 1) * 1.0);
    for(int i = 0; i < m; i++)
        e[i].fw = ((double)e[i].w - ave) * ((double)e[i].w - 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);
            fall += e[i].fw;
            all += e[i].w;
            cnt++;
        }
        if(cnt == n - 1)
            break;
    }
    if(all == sum)
        ans = min(ans, fall);
}

int main()
{
    int ca = 1;
    while(scanf("%d %d", &n, &m) != EOF && (m + n))
    {
        minv = 0;
        maxv = 0;
        ans = MAX;
        for(int i = 0; i < m; i++)
        {
            scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w);
            a[i] = e[i].w;
        }
        sort(a, a + m);
        for(int i = 0; i < n - 1; i++)
            minv += a[i];
        sort(a, a + m, cmp1);
        for(int i = 0; i < n - 1; i++)
            maxv += a[i];
        for(int i = minv; i <= maxv; i++)
            Kruskal(i);
        printf("Case %d: %.2f\n", ca++, ans / (double) (n - 1));
    }
}