藍(lán)橋杯 最小方差生成樹問題
極客小將2022-04-11-
問題描述給定帶權(quán)無向圖，求出一顆方差最小的生成樹。輸入格式輸入多組測試數(shù)據(jù)。第一行為N,M，依次是點(diǎn)數(shù)和邊數(shù)。接下來M行，每行三個(gè)整數(shù)U,V,W，代表連接U,V的邊，和權(quán)值W。保證圖連通。n=m=0標(biāo)志著測試文件的結(jié)束。輸出格式對于每組數(shù)據(jù)，輸出最小方差，四舍五入到0.01。輸
問題描述
給定帶權(quán)無向圖，求出一顆方差最小的生成樹。
輸入格式
輸入多組測試數(shù)據(jù)。第一行為N,M，依次是點(diǎn)數(shù)和邊數(shù)。接下來M行，每行三個(gè)整數(shù)U,V,W，代表連接U,V的邊，和權(quán)值W。保證圖連通。n=m=0標(biāo)志著測試文件的結(jié)束。
輸出格式
對于每組數(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
數(shù)據(jù)規(guī)模與約定
1<=U,V<=N<=50,N-1<=M<=1000,0<=W<=50。數(shù)據(jù)不超過5組。
- 上一篇
2021藍(lán)橋杯python組異或數(shù)列試題
2021藍(lán)橋杯python組異或數(shù)列試題
- 下一篇
藍(lán)橋杯 C最短路問題
問題描述給定一個(gè)n個(gè)頂點(diǎn)，m條邊的有向圖（其中某些邊權(quán)可能為負(fù)，但保證沒有負(fù)環(huán)）。請你計(jì)算從1號點(diǎn)到其他點(diǎn)的最短路（頂點(diǎn)從1到n編號）。輸入格式第一行兩個(gè)整數(shù)n, m。接下來的m行，每行有三個(gè)整數(shù)u, v, l，表示u到v有一條長度為l的邊。輸出格式共n-1行，第i行表示1號點(diǎn)到
相關(guān)資訊
