題目 1937:
藍(lán)橋杯算法提高VIP-最小方差生成樹
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 83 解決: 0
題目描述
給定帶權(quán)無向圖，求出一顆方差最小的生成樹。
輸入格式
輸入多組測(cè)試數(shù)據(jù)。第一行為N,M，依次是點(diǎn)數(shù)和邊數(shù)。接下來M行，每行三個(gè)整數(shù)U,V,W，代表連接U,V的邊，和權(quán)值W。保證圖連通。n=m=0標(biāo)志著測(cè)試文件的結(jié)束。
輸出格式
對(duì)于每組數(shù)據(jù)，輸出最小方差，四舍五入到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
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點(diǎn)擊這里了解課程詳情
標(biāo)簽