P95096

最小方差生成树

难度 未定 图论
讨论 统计 0通过 0提交 旧版界面
时间限制 1 秒 内存限制 256 MB

题目描述

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

输入

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

输出

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

样例

样例 1
输入
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

使用最小生成树。

锦囊2

枚举最小生成树可能的边权平均值,将边权设置为原边权减去平均值的平方,然后求最小生成树。

来源

蓝桥杯

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交