2016 10 28考试 dp 乱搞 树状数组

乱搞题，题目中要求求方差最小的生成树，看起来比较无从下手，那么结合方差的性质可知，如果加入的边边权差尽量小，方差一定相应变小，这样就将方差问题转化为排序问题。之后考虑题目的数据范围，可以发现题目中的边的边权均较小，由此可以直接枚举平均值，每次按照abs(p[x].val - w_average)来排序，加入直到形成生成树，求出此时方差并更新答案。
注意，由于枚举平均值可能带来的精度问题，建议转而枚举边的总值

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
const int maxn = 1000 + 10;
const int maxm = 10000 + 10;
struct data {
    int from;
    int to;
    int val;    
};
data p[maxm];
int tim;
int n, m;
int minw, maxw;
bool flag[maxn];
double t_average;
double fc;
double ans = 0x7fffffff;
int father[maxn];

int getfather(int x) {
    if (father[x] == x) return (x);
    return (father[x] = getfather(father[x]));
}

bool cmp1 (data aa, data bb) {
    return (aa.val < bb.val);
}

bool cmp2(data aa, data bb) {
    double a1 = (double) aa.val;
    double a2 = (double) bb.val;
    a1 = fabs(a1 - t_average);
    a2 = fabs(a2 - t_average);
    return (a1 < a2);
}

int main () {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    while (scanf("%d %d", &n, &m) == 2 && n && m) {
        tim++;
        printf("Case %d: ", tim);
        for (int i = 1; i <= m; i++) scanf("%d %d %d", &p[i].from, &p[i].to, &p[i].val);
        std :: sort(p + 1, p + m + 1, cmp1);
        for (int i = 1; i < n; i++) {
            minw += p[i].val;
            maxw += p[m - i + 1].val;
        }   
        for (int k = minw; k <= maxw; k++) {
            memset(flag, 0, sizeof(flag));
            for (int j = 1; j <= n; j++ ) father[j] = j;
            t_average = (double) k / (double) (n-1);
            std :: sort(p + 1, p + m + 1, cmp2);
            int t_sumw = 0;
            for (int i = 1; i <= m; i++) {
                int fx = getfather(p[i].from);
                int fy = getfather(p[i].to);
                if (fx != fy) {
                    father[fx] = fy;
                    flag[i] = 1;
                    t_sumw += p[i].val;
                }
            }
            if (t_sumw == k) {
                fc = 0;
                for (int i = 1; i <= m; i++) 
                    if (flag[i]) fc += ((double)p[i].val - t_average) * ((double)p[i].val - t_average);
                if (fc < ans) ans = fc;
            }
        }
        ans = ans / (double) (n-1);
        printf("%.2lfn", ans);
    }
}

（编辑：三明站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!