BZOJ 3754 最小方差生成树

晚上逛了下BZOJ，发现又挂了3道新的题目，瞄了一眼发现就这道题目会做，顺手切了来写个题解。

题目大意

给你一个无向连通图，求出一个生成树使得边权的标准差最小。

数据规模：\(1 \le n \le 100, 1 \le m \le 2000, 1 \le \text{边权} \le 100\)

题目分析

首先我们知道只需要考虑\(\displaystyle \sum_{i=1}^{n-1}{(w_i-\overline{w})^2}\)最小即可。不妨假设我们已经知道了\(\overline{w}\)，那么只要将\((w_i-\overline{w})^2\)当做边权做一遍最小生成树即可。现在我们不知道\(\overline{w}\)，但是我们却可以确定边权的相对位置。

考虑两条边\(w_i,w_j\)，对应为\(w_i^\prime=(w_i-\overline{w})^2,w_j^\prime=(w_j-\overline{w})^2\)，然后令\(w_0=\frac{w_i+w_j}{2}\)，当\(\overline{w} = w_0\)时，\(w_i^\prime=w_j^\prime\)；当\(\overline{w} \ne w_0\)时，\(w_i^\prime\)和\(w_j^\prime\)可以确定一个相对大小。也就是说只有\(\overline{w}\)在变成\(w_0=\frac{w_i+w_j}{2}\)的时候\(w_i^\prime\)和\(w_j^\prime\)的相对位置才会发生改变（这么一写，感觉和我出过的某道题目好像。。。）。

于是我们只要枚举所有的\(w_0=\frac{w_i+w_j}{2}\)，做一遍最小生成树即可。然后复杂度是\(O(m^3\log m)\)，大概会超时。这时候考虑\(1 \le \text{边权} \le 100\)这个条件，我们可以发现\(w_0=\frac{w_i+w_j}{2}\)最多可能只有200个，也就是只要枚举这200个值即可，复杂度\(O(200m\log m)\)。

贴个代码，仅供参考

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int MAXN = 105, MAXM = 2005;
const double eps = 1e-8;
pair<double, PII> g[MAXM];
int dsu[MAXN], edge[MAXN];
double cost[MAXM];
int n, m;

int get(int x) {return dsu[x] == x ? x : dsu[x] = get(dsu[x]);}
inline double sqr(double x) {return x * x;}
inline bool cmp(int i, int j) {return cost[i] + eps < cost[j];}

double kruskal(int num) {
    static int id[MAXM];
    double sum = 0, avg = 0.5 * num + 0.1;
    for (int i = 0; i < m; ++ i) {
        id[i] = i, cost[i] = sqr(g[i].first - avg);
    }
    sort(id, id + m, cmp);
    for (int i = 1; i <= n; ++ i) dsu[i] = i;
    int cnt = 0;
    for (int _ = 0; _ < m; ++ _) {
        int i = id[_];
        int x = get(g[i].second.first), y = get(g[i].second.second);
        if (x != y) {
            dsu[x] = y;
            edge[cnt ++] = g[i].first;
            sum += g[i].first;
        }
        if (cnt == n - 1) break;
    }
    avg = 1.0 * sum / (n - 1); sum = 0;
    for (int i = 0; i < cnt; ++ i) {
        sum += sqr(edge[i] - avg);
    }
    return sum / (n - 1);
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; ++ i) {
        int x, y, z; scanf("%d %d %d", &x, &y, &z);
        g[i] = make_pair(z, PII(x, y));
    }
    double ret = 1e100;
    for (int i = 0; i < 205; ++ i) {
        ret = min(ret, kruskal(i));
    }
    if (n == 1) ret = 0;
    printf("%.4f\n", sqrt(ret));
}

• Relative Posts