Description：
求一个图的最小方差生成树。(1<=U,V<=N<=50,N-1<=M<=1000,0<=W<=50)
Analysis：
枚举平均值（精确到0.01）
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 60,M = 1100;
struct edge{
int u,v;
double w;
bool operator < (const edge &a) const {
return w < a.w;
}
}e[M << 1],e1[M << 1];
int f[N],n,m,cnt;
double ave,ans;
int find(int p)
{
if(f[p] == p) return p;
return f[p] = find(f[p]);
}
void Merge(int a,int b)
{
a = find(a);
b = find(b);
if(rand()%2 == 1) f[a] = b;
else f[b] = a;
}
void kruscal()
{
for(int i = 1;i <= m;++i)
{
e1[i].u = e[i].u;
e1[i].v = e[i].v;
e1[i].w = (e[i].w - ave)*(e[i].w - ave);
}
sort(e1+1,e1+1+m);
double crt = 0;
for(int i = 1;i <= n;++i) f[i] = i;
for(int i = 1;i <= m;++i)
{
int u = find(e1[i].u),v = find(e1[i].v);
if(u != v)
{
Merge(u,v);
crt += e1[i].w;
}
}
//printf("%.2lf
",crt);
ans = min(crt,ans);
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
if(n == 0) break;
cnt++;
for(int i = 1;i <= m;++i)
{
scanf("%d%d%lf",&e[i].u,&e[i].v,&e[i].w);
}
ans = 23333333.233;
for(ave = 0.00;ave <= 50;ave += 0.01)
{
kruscal();
}
printf("Case %d: %.2lf
",cnt,ans/(n-1));
}
return 0;
}