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

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

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

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