1843 問題 E: 藍(lán)橋杯2017年第八屆真題-觀光鐵路
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 152 解決: 76
題目描述
跳蚤國(guó)正在大力發(fā)展旅游業(yè)，每個(gè)城市都被打造成了旅游景點(diǎn)。
許多跳蚤想去其他城市旅游，但是由于跳得比較慢，它們的愿望難以實(shí)現(xiàn)。這時(shí)，小C聽說有一種叫做火車的交通工具，在鐵路上跑得很快，便抓住了商機(jī)，創(chuàng)立了一家鐵路公司，向跳蚤國(guó)王請(qǐng)示在每?jī)蓚€(gè)城市之間都修建鐵路。
然而，由于小C不會(huì)扳道岔，火車到一個(gè)城市以后只能保證不原路返回，而會(huì)隨機(jī)等概率地駛向與這個(gè)城市有鐵路連接的另外一個(gè)城市。
跳蚤國(guó)王向廣大居民征求意見，結(jié)果跳蚤們不太滿意，因?yàn)檫@樣修建鐵路以后有可能只游覽了3個(gè)城市（含出發(fā)的城市）以后就回來了，它們希望能多游覽幾個(gè)城市。于是跳蚤國(guó)王要求小C提供一個(gè)方案，使得每只跳蚤坐上火車后能多游覽幾個(gè)城市才回來。
小C提供了一種方案給跳蚤國(guó)王。跳蚤國(guó)王想知道這個(gè)方案中每個(gè)城市的居民旅游的期望時(shí)間（設(shè)火車經(jīng)過每段鐵路的時(shí)間都為1），請(qǐng)你來幫跳蚤國(guó)王。
輸入
輸入的第一行包含兩個(gè)正整數(shù)n、m，其中n表示城市的數(shù)量，m表示方案中的鐵路條數(shù)。
接下來m行，每行包含兩個(gè)正整數(shù)u、v，表示方案中城市u和城市v之間有一條鐵路。
保證方案中無重邊無自環(huán)，每?jī)蓚€(gè)城市之間都能經(jīng)過鐵路直接或間接到達(dá)，且火車由任意一條鐵路到任意一個(gè)城市以后一定有路可走。
輸出
輸出n行，第i行包含一個(gè)實(shí)數(shù)ti，表示方案中城市i的居民旅游的期望時(shí)間。你應(yīng)當(dāng)輸出足夠多的小數(shù)位數(shù)，以保證輸出的值和真實(shí)值之間的絕對(duì)或相對(duì)誤差不超過1e-9。
樣例輸出
3.333333333333
5.000000000000
3.333333333333
5.000000000000
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點(diǎn)擊這里了解課程詳情