算法提高 最小方差生成树  
时间限制：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组。

蓝桥杯的测试数据好像有问题。。。

 

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <vector>
  4 #include <queue>
  5 #include <map>
  6 #include <cmath>
  7 #include <stack>
  8 #include <cstring>
  9 #include <algorithm>
 10 #include <cstdlib>
 11 #define FOR(i,x,n) for(long i=x;i<n;i++)
 12 #define ll long long int
 13 #define INF 0x3f3f3f3f
 14 #define MOD 1000000007
 15 #define MAX_N 60
 16 #define MAX_M 1005
 17 
 18 using namespace std;
 19 
 20 struct node{
 21     int u,v;
 22     double wPrior;
 23     double wNow;
 24 };
 25 node graph[MAX_M];//储存边
 26 int N,M;//点，边
 27 int a[60];//并查集数组
 28 
 29 void init(){//并查集数组初始化
 30     FOR(i,1,61){
 31         a[i]=i;
 32     }
 33 }
 34 
 35 bool cmp(node a,node b){
 36     return a.wNow<b.wNow;
 37 }
 38 
 39 int findCaptain(int t){//寻找队长
 40     if(a[t]==t){
 41         return t;
 42     }else{
 43         return a[t]=findCaptain(a[t]);//路径压缩
 44     }
 45 }
 46 
 47 bool judge(int t1,int t2){//判断是否在一组内
 48     return findCaptain(t1)==findCaptain(t2);
 49 }
 50 
 51 void unionPoint(int t1,int t2){//合并两点
 52     int tt=findCaptain(t1);
 53     int ttt=findCaptain(t2);
 54     a[tt]=ttt;
 55 }
 56 
 57 double kruskal(int sum){//kruskal最小生成树
 58     int edgeCount=0;
 59     double sum2=0;
 60     double sum3=0;
 61     double ave=sum*1.0/(N-1);
 62     FOR(i,0,M){
 63         graph[i].wNow=(graph[i].wPrior-ave)*(graph[i].wPrior-ave);
 64     }
 65     sort(graph,graph+M,cmp);//按边权从小到大排序
 66     FOR(i,0,M){
 67         int t1=graph[i].u;
 68         int t2=graph[i].v;
 69         if(!judge(t1,t2)){
 70             unionPoint(t1,t2);
 71             edgeCount++;
 72             sum2+=graph[i].wPrior;
 73             sum3+=graph[i].wNow;
 74             if(edgeCount==N-1){
 75                 break;
 76             }
 77         }
 78     }
 79     if(sum==(int)sum2){
 80         return sum3;
 81     }else{
 82         return INF*1.0;
 83     }
 84 }
 85 
 86 int main()
 87 {
 88     //freopen("input1.txt", "r", stdin);
 89     //freopen("data.out", "w", stdout);
 90     double t[1005];
 91     int caseCount=0;
 92     double minVariance=INF*1.0;
 93     while(~scanf("%d %d",&N,&M)&&(N+M)){
 94         FOR(i,0,M){
 95             scanf("%d %d %lf",&graph[i].u,&graph[i].v,&graph[i].wPrior);
 96             t[i]=graph[i].wPrior;
 97         }
 98         sort(t,t+M);
 99         double minn=0,maxx=0;
100         FOR(i,0,N-1){//找出可能的最小的average*(n-1)
101             minn+=t[i];
102         }
103         FOR(i,M-N+1,M){//找出最大的average*(n-1)
104             maxx+=t[i];
105         }
106         minVariance=INF*1.0;
107         FOR(i,minn,maxx+1){
108             init();
109             double ans=kruskal(i);
110             minVariance=min(minVariance,ans);
111         }
112         printf("Case %d: %.2f\n",++caseCount,minVariance/(N-1));
113 
114     }
115 
116     //fclose(stdin);
117     //fclose(stdout);
118     return 0;
119 }
View Code