信息學(xué)集訓(xùn)隊作業(yè)

1、WC2007模擬題 命題人 顧研第4頁 共4頁道路規(guī)劃road【問題描述】Henryy國這一塊廣大而富庶的土地不斷對Henryy國的一代一代新人提出新的挑戰(zhàn)。在思想與行動上代代子民都勇于面對挑戰(zhàn)，也因而造就國家的進(jìn)步。當(dāng)高山擋住去路，Henryy國人就繞道或穿鑿高山，建造公路和鐵路；洪水威脅時，Henryy國人建造水壩與堤防遏阻水勢；在干旱地區(qū)，Henryy國人建造偉大的灌溉系統(tǒng)。為了騁馳于廣大的田野中，Henryy國人更開創(chuàng)了龐大的運輸系統(tǒng)以及通訊系統(tǒng)。在Henryy國有n個城市，m條寬敞的雙向高速公路使任意兩座城市都可相互達(dá)到。然而很不幸Henryy國是個地震頻發(fā)的國家。一次強烈的地震完全

2、可以使得某條高速公路中斷通行能力，因此有可能使兩個城市不能互達(dá)。而且你也清楚，維修道路是一件費時費力的事情，這也阻礙了Henryy隨時巡游。作為Henryy國的交通局局長，現(xiàn)在必須確定通過修最少的一些道路來為Henryy解決這個問題，使得無論那一條道路被破壞，任意兩個城市依然能互達(dá)?！据斎胛募康谝恍袃蓚€整數(shù)n，m。接下來m行，每行兩個整數(shù)a和b（1a,bn），表示a與b之間有一條高速公路。【輸出文件】第一行一個整數(shù)k，表示最少需要新修道路的條數(shù)。接下來k行，描述每條你要新修的路連接的城市的編號?！緲永斎搿? 31 22 32 4【輸出文件】21 41 3【數(shù)據(jù)約定】3n2500。n-1m2

3、0000。對于30%的數(shù)據(jù)有3mn11。對于40%的數(shù)據(jù)有m=4時，不同的連接方法將會導(dǎo)致不同的結(jié)果。這是為什么呢？因為像左圖，連接了兩個葉子合并之后，又產(chǎn)生了一個新的葉子。因此我們添邊的時候，首先找到一個葉子，然后開始dfs，直到找到另一個葉子且路徑上連出去的非路徑邊至少為2。把這兩個點連邊并收縮。重復(fù)這一過程，直到葉子數(shù)為2或3。會不會不存在這樣的連邊呢？我們考慮反證法，如果一個葉子到另一個葉子路徑上連出去的非路徑邊為0，則必然只有兩個葉子。如果為1，且順著這個分支走出去的葉子連出去的非路徑邊也為1，則必然只有3個葉子。在實現(xiàn)方面，由于數(shù)據(jù)比較小，我們可以不用進(jìn)行刪邊、合并的過程，只要標(biāo)一個號就可以了。這個算法的復(fù)雜度是的。在測試中，余林韻同學(xué)提出了一種基于dfs遍歷的構(gòu)造方法：如果現(xiàn)在遍歷到某個節(jié)點A，遍歷它的若干個兒子后它有多于2個葉子結(jié)點，則把不同的兒子間的葉子