2018-team4-modules-最小方差生成树

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
//构成生成树的所有边的方差最小
#define EPS (1.0 / (n - 1))
struct Edge{
    int x,y,len;
    double temp;
    bool operator <(const Edge &a)const {return len < a.len;}
    void Read(){read(x);read(y);read(len);}
}G[maxn];
int n,m;
int fa[maxn];
int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}
inline int MST(){
    for(int i = 1; i <= n; ++i) fa[i] = i;
    int re = 0;
    for(int i = 1; i <= m; ++i) {
        int fx = find(G[i].x);
        int fy = find(G[i].y);
        if(fx != fy) {
            fa[fx] = fy;
            re += G[i].len;
        }
    }
    return re;
}
inline bool cmp(const Edge &a,const Edge &b){return a.temp < b.temp;}
inline double Calc(double average){
    for(int i = 1; i <= n; ++i) fa[i] = i;
    for(int i = 1; i <= m; ++i)
        G[i].temp = (average - G[i].len) * (average - G[i].len);
    sort(G + 1,G + m + 1,cmp);
    double re = 0.0;
    for(int i = 1; i <= m; ++i) {
        int fx = find(G[i].x);
        int fy = find(G[i].y);
        if(fx != fy) {
            fa[fx] = fy;
            re += G[i].temp;
        }
    }
    return re / (n - 1);
}
int main(){
    read(n);read(m);
    for(int i = 1; i <= m; ++i) G[i].Read();
    sort(G + 1,G + m + 1);
    double range_min = (double)MST() / (n - 1);
    reverse(G + 1,G + m + 1);
    double range_max = (double)MST() / (n - 1);
    double ans = inf;
    for(int i = 0; EPS*i + range_min <= range_max; ++i)
        ans = min(ans,Calc(EPS*i + range_min));
    printf("%.4lf\n",ans);
    return 0;
}
}}}

//构成生成树的所有边的方差最小
#define EPS (1.0 / (n - 1))
struct Edge{
    int x,y,len;
    double temp;
    bool operator <(const Edge &a)const {return len < a.len;}
    void Read(){read(x);read(y);read(len);}
}G[maxn];
int n,m;
int fa[maxn];
int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}
inline int MST(){
    for(int i = 1; i <= n; ++i) fa[i] = i;
    int re = 0;
    for(int i = 1; i <= m; ++i) {
        int fx = find(G[i].x);
        int fy = find(G[i].y);
        if(fx != fy) {
            fa[fx] = fy;
            re += G[i].len;
        }
    }
    return re;
}
inline bool cmp(const Edge &a,const Edge &b){return a.temp < b.temp;}
inline double Calc(double average){
    for(int i = 1; i <= n; ++i) fa[i] = i;
    for(int i = 1; i <= m; ++i)
        G[i].temp = (average - G[i].len) * (average - G[i].len);
    sort(G + 1,G + m + 1,cmp);
    double re = 0.0;
    for(int i = 1; i <= m; ++i) {
        int fx = find(G[i].x);
        int fy = find(G[i].y);
        if(fx != fy) {
            fa[fx] = fy;
            re += G[i].temp;
        }
    }
    return re / (n - 1);
}
int main(){
    read(n);read(m);
    for(int i = 1; i <= m; ++i) G[i].Read();
    sort(G + 1,G + m + 1);
    double range_min = (double)MST() / (n - 1);
    reverse(G + 1,G + m + 1);
    double range_max = (double)MST() / (n - 1);
    double ans = inf;
    for(int i = 0; EPS*i + range_min <= range_max; ++i)
        ans = min(ans,Calc(EPS*i + range_min));
    printf("%.4lf\n",ans);
    return 0;
}