蓝桥杯 ADV-5 最小方差生成树 （试题解析）

试题 算法提高 最小方差生成树

提交此题   评测记录  

资源限制

时间限制：1.0s   内存限制：256.0MB

问题描述

给定带权无向图，求出一颗方差最小的生成树。

输入格式

输入多组测试数据。第一行为N,M，依次是点数和边数。接下来M行，每行三个整数U,V,W，代表连接U,V的边，和权值W。保证图连通。n=m=0标志着测试文件的结束。

输出格式

对于每组数据，输出最小方差，四舍五入到0.01。输出格式按照样例。

样例输入

4 5
1 2 1
2 3 2
3 4 2
4 1 1
2 4 3
4 6
1 2 1
2 3 2
3 4 3
4 1 1
2 4 3
1 3 3
0 0

样例输出

Case 1: 0.22
Case 2: 0.00

数据规模与约定

1<=U,V<=N<=50,N-1<=M<=1000,0<=W<=50。数据不超过5组。

解题思路：一开始我准备用Prim 算法，然而无从下手。。。后来看了大佬的代码，才明白，用Kruskal 算法，遍历 最小生成树 路径和 所有可能出现的 情况（即从minW -> maxW ），每一次遍历 更新 最小的 方差和 res。

代码如下：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Edge{
    int from,to;
    int W;
    double var;
}E[1010];

int N,M;
int father[52];
double res;
int tmp[1010];

void init(){
    
    for(int i=1;i<=N;i++){
        father[i]=i;
    }
    
}

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

bool Same(int x,int y){
    return Find(x)==Find(y);
}

void unionSet(int x,int y){
    int u=Find(x),v=Find(y);
    if(u==v)
        return ;
    father[u]=v;
}

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

void Kruskal(int sum){
    init();
//    cout<<"start to Kruskal"<<endl;
    double avg=1.0*sum/(N-1);
    
    for(int i=1;i<=M;i++){
        E[i].var=(E[i].W-avg)*(E[i].W-avg);
    }
    sort(E+1,E+1+M,cmp);
    
    int cnt=0;
    double varSum=0;
    int wSum=0;
    
    for(int i=1;i<=M;i++){
        if( Same(E[i].from,E[i].to) )
            continue;
    //    cout<<"center of Kruskal"<<endl;
        
        unionSet(E[i].from,E[i].to);
        varSum+=E[i].var;
        wSum+=E[i].W;
        cnt++;
        
        if(cnt==N-1)
            break;
    }
    
    if(wSum==sum){
        res=min(res,varSum);
    //    cout<<varSum/(N-1)<<endl;
    }
//    cout<<"Kruskal is over!"<<endl;
}

int main(int argc, char** argv) {
    vector<double>    vkt;

    while(1){
        cin>>N>>M;
        if(N==0 && M==0)
            break;
            
        
        res=65535;
        for(int i=1;i<=M;i++){
            cin>>E[i].from>>E[i].to>>E[i].W;
            tmp[i]=E[i].W;
        }
            
        int minW=0,maxW=0;
        
        sort(tmp,tmp+1+M);
        
        for(int i=1;i<=N-1;i++)
            minW+=tmp[i];
            
        for(int i=M;i>=M-N+2;i--)
            maxW+=tmp[i];
            
        for(int i = minW; i <= maxW; i++)
            Kruskal(i);
            
        res=res/(N-1);
        vkt.push_back(res);
   
    }

    for(int i=0;i<vkt.size();i++){
        printf("Case %d: %.2f\n", i+1, vkt[i]);
    }

    return 0;
}