BZOJ 3754 - Tree之最小方差树

#图论 #生成树 #枚举
Published on 2016-06-27

题目地址

描述

Wayne 在玩儿一个很有趣的游戏。在游戏中，Wayne 建造了 n(n≤100)n(n\le 100) 个城市，现在他想在这些城市间修一些公路，当然并不是任意两个城市间都能修，为了道路系统的美观，一共只有 m(m≤2000)m(m\le 2000) 对城市间能修公路，即有若干三元组 (ui,vi,ci)(ci≤100)(u_i,v_i,c_i)(c_i\le 100) 表示 uiu_i 和 viv_i 间有一条长度为 cic_i 的双向道路。当然，游戏保证了，若所有道路都修建，那么任意两城市可以互相到达。Wayne 拥有恰好 n−1n-1 支修建队，每支队伍能且仅能修一条道路。当然，修建长度越大，修建的劳累度也越高，游戏设定是修建长度为 cc 的公路就会有 cc 的劳累度。当所有的队伍完工后，整个城市群必须连通，而这些修建队伍们会看看其他队伍的劳累情况，若劳累情况差异过大，可能就会引发骚动，不利于社会和谐发展。Wayne 对这个问题非常头疼，于是他想知道，这 n−1n - 1 支队伍劳累度的标准差最小能有多少。
标准差的定为：设有 nn 个数，分别为 aia_i，它们的平均数为 a¯\bar a,那么标准差就是：

∑0≤i<n(a−a¯)2N\sqrt{\frac{\sum_{0\le i < n}(a - \bar a) ^ 2}{N}}

分析

由于平均值的存在，使得问题非常棘手，怎么办呢？观察到权值很小，枚举！
我们枚举平均值 xx，然后将每条边的权值变为 (c−x)2(c - x)^2，做一次最小生成树，更新答案。嗯？求出的“这棵树”平均值有可能不是 xx？我们将上面的式子展开看看：

∑0≤i<n(a−a¯)2=∑0≤i<na2−2aa¯+a¯2=(∑0≤i<na2)−2(∑0≤i<na2)a¯+na¯2\sum_{0\le i < n}(a - \bar a) ^ 2 = \sum_{0\le i < n}a ^ 2 - 2 a \bar a + {\bar a} ^ 2=(\sum_{0\le i < n}a ^ 2)- 2(\sum_{0\le i < n}a ^ 2)\bar a+n\bar a^2

以 a¯\bar a 为主元，根据二次函数的单调性，这个函数将在 x=∑0≤i<nainx = \frac {\sum_{0\le i < n}a_i}{n} 时取到最值，就是说如果我们没有恰好枚举到“这棵树”的平均值，那么得到标准差不会比它真实的标准差大。这一点保证我们可以枚举任意值而不用担心答案不合法。

枚举 xx 做最小生成树，不管 xx 是否就是“这棵树”的平均值，求出的答案一定是 xx 下最优的，虽然弄出的“这棵树”的真实标准差小于等于现在求出的值。

我们考虑能不能枚举到最优的树，假设最优的树的平均值是 avg\mathrm{avg}，那么根据峰值的取值点以及做的是最小生成树，我们枚举到 x=avgx = \mathrm{avg} 时一定能枚举到这个树，

没做出来的原因：没有观察权值范围，不利用题目的特殊性质，盲目的思考。
出题人想考什么：枚举（以式子的峰值为依据）
总结：对于经典问题的变形，要用敏锐的眼光观察到数据范围以及题目的特殊性，从特殊性入手。

代码

//  Created by Sengxian on 6/27/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 3754 枚举
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 100 + 3;
struct edge {
    int from, to, realCost;
    double cost;
    edge(int from, int to, int realCost): from(from), to(to), realCost(realCost), cost(realCost) {}
    bool operator < (const edge &ano) const {
        return cost < ano.cost;
    }
};

vector<edge> edges;
int n, m, fa[maxn];

inline void init(int n) {
    for (int i = 0; i < n; ++i) fa[i] = i;
}

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

inline void unite(int x, int y) {
    x = find(x), y = find(y);
    fa[x] = y;
}

int Kruskal_min() {
    int ans = 0, cnt = 0;
    init(n);
    for (int i = 0; i < (int)edges.size(); ++i) {
        const edge &e = edges[i];
        if (find(e.to) != find(e.from)) {
            unite(e.to, e.from);
            ans += e.cost;
            cnt++;
        }
        if (cnt == n - 1) break;
    }
    return ans;
}

int Kruskal_max() {
    int ans = 0, cnt = 0;
    init(n);
    for (int i = (int)edges.size() - 1; ~i; --i) {
        const edge &e = edges[i];
        if (find(e.to) != find(e.from)) {
            unite(e.to, e.from);
            ans += e.cost;
            cnt++;
        }
        if (cnt == n - 1) break;
    }
    return ans;
}

double calc(int sum) {
    double avg = (double)sum / (n - 1), ans = 0;
    int cnt = 0;
    init(n);
    for (int i = 0; i < (int)edges.size(); ++i) edges[i].cost = (edges[i].realCost - avg) * (edges[i].realCost - avg);
    sort(edges.begin(), edges.end());
    for (int i = 0; i < (int)edges.size(); ++i) {
        const edge &e = edges[i];
        if (find(e.to) != find(e.from)) {
            unite(e.to, e.from);
            ans += e.cost;
            cnt++;
        }
        if (cnt == n - 1) break;
    }
    return sqrt(ans / (n - 1));
}

int main() {
    n = ReadInt(), m = ReadInt();
    for (int i = 0; i < m; ++i) {
        int f = ReadInt() - 1, t = ReadInt() - 1, c = ReadInt();
        edges.push_back(edge(f, t, c));
    }
    sort(edges.begin(), edges.end());
    int l = Kruskal_min(), r = Kruskal_max();
    double ans = 1e300;
    for (int i = l; i <= r; ++i) ans = min(ans, calc(i));
    printf("%.4lf\n", ans);
    return 0;
}
BZOJ 2959 - 长跑