/ＪＳＯＩ2００８江蘇省代表隊組隊第三輪選拔賽本次競賽共分兩試，本試卷為第二試第二試試題競賽時間：２0０8年4月28日7:30-12:30試題說明試題名稱分值源文件輸入文件輸出文件限時星球大戰(zhàn)85sｔarｗarstarwａｒ.instarwar。out≤３s魔獸地圖100DotＲＤoｔR.inＤoｔＲ．ｏｕt≤2ｓ巨額獎金１15AwａrdＡwａrd．iｎAwａrd.oｕt≤1ｓ分數分布第一試共三道題，滿分為300分.文件命名選手提交源程序,名字見每題標題，并最終拷貝到指定硬盤的相應目錄。源文件的名字應與編譯后的可執(zhí)行程序同名。選手程序應從。IN中讀入輸入數據，不需要進行判錯處理。執(zhí)行結果存放到.ＯUT中。輸入輸出文件均不需指定目錄.程序運行要求評測時采用黑盒測試.每題均為十個測試點。對每個測試點有一定的時間限制和分數.選手程序必須在此時限內運行結束并輸出正確的結果才能得到這個點的分數。程序運行時僅對指定的文件讀寫，不應在屏幕上顯示任何信息或者等待鍵盤輸入.文件各行所有數據均用一個空格隔開。輸出結果應按題面要求，不應有多余的字符。

題一星球大戰(zhàn)ＳtarWar/．IN/.OUT/。PＡＳ/。EXE問題描述很久以前，在一個遙遠的銀河系……對反抗軍來說,這是一個黑暗的時刻。雖然帝國軍的終極武器“死亡星球”已經被摧毀，帝國的軍隊仍然把反抗軍從隱藏的軍事基地中趕出，并在整個銀河系展開追逐。Alongtimeagoinagalaxyfar,faraway…ItisadarktimefortheRebellion.AlthoughtheDeathStarhasbeendestroyed,ImperialtroopshavedriventheRebelforcesfromtheirhiddenbaseandpursuedthemacrossthegalaxy.——摘自StarWarsEpisodeV,TheEmpireStrikesBack考慮到邪惡的帝國完全有能力在短時間內制造出“死亡星球"的替代品，為了避免被一次全部殲滅，反抗軍的指揮官決定把部隊分散在很多星球上.可是，這樣會帶來通訊上的問題。某些星球之間可以通過“以太”隧道直接通訊，而沒有隧道相連的星球之間的通訊就需要其他星球幫忙轉發(fā)。因此，只有兩個星球之間存在一條由“以太”隧道拼接成的路徑，它們才可以正常通訊.銀河歷2008年4月1日凌晨，反抗軍最擔心的事情還是發(fā)生了。反抗軍司令部收到間諜的秘密通知:帝國軍成功制造出第二代“死亡星球",并將依次摧毀如下星球（星球列表略）.指揮官希望迅速計算出每次攻擊之后通訊網絡的連通情況，即反叛軍所占據的星球被分成了多少個連通支，從而幫助決定在何時發(fā)動反擊。輸入輸入文件starｗar。ｉn的第一行包含兩個整數N(2≤N≤2M)和Ｍ(1≤Ｍ≤200，0００），分別表示星球的數目和“以太”隧道的數目.星球用0到N–１的整數編號。接下來的M行,每行包含兩個整數X和Ｙ(０≤X≠Ｙ〈N）,表示星球Ｘ和星球Y之間有“以太"隧道,可以直接通訊.接下來的一行包含一個整數K,表示將遭受攻擊的星球的數目.接下來的K行,每行一個整數,按照順序列出了帝國軍的攻擊目標.這Ｋ個數互不相同，且都在0到N–１的范圍內.輸出請將輸出寫至文件starｗaｒ。out。輸出文件應該包含K＋1行，每行一個整數。第一個整數表示開始時通訊網絡的連通支個數.接下來的第I（1≤I≤K）個整數，表示在攻擊列表上的第I個星球被摧毀后，通訊網絡的連通支個數。樣例stａrwar.insｔarwar.out813011６655００612２33４45７172７636516３57111233樣例說明220513674題二魔獸地圖DotR／．IN/．ＯUＴ/．PAS/。EXE問題描述DotＲ（ＤefeｎseｏftｈeRｏbｏtｓ）Alｌstarｓ是一個風靡全球的魔獸地圖,它的規(guī)則簡單于同樣流行的地圖DotA（ＤefｅnsｅoｆthｅＡｎcientｓ）Allstars。DotR里面的英雄只有一個屬性——力量。它們需要購買裝備來提升自己的力量值。每件裝備都可以使佩戴它的英雄的力量值提高固定的點數，所以英雄的力量值等于它購買的所有裝備的力量值之和。裝備分為基本裝備和高級裝備兩種，基本裝備可以直接從商店里面用金幣購買,而高級裝備需要用基本裝備或者較低級的高級裝備來合成，合成不需要附加的金幣.裝備的合成路線圖可以用一棵樹來表示，如下圖所示.例如，SanｇｅanｄYasｈａ的合成需要Saｎge、Yasha和SａngeanｄＹasｈaRｅcipeScroll三樣物品。其中Sａｎgｅ又要用OgreAxe、BelｔofGｉａntStｒeｎgｔh和ＳａngeReｃiｐeSｃｒｏｌｌ合成。SangeandYashaSangeandYashaSangeYashaaaOgreAxeBeltofGiantStrengthSangeandYashaRecipeScrollSangeRecipeScrollYashaRecipeScrollBladeofAlacrityBootsofElvenskin每件基本裝備都有數量限制，這限制了你不能無限制地合成某些性價比很高的裝備?，F在,英雄Sｐectrｅ有Ｍ個金幣，它想用這些錢購買裝備使自己的力量值盡量高。你能幫幫它嗎？它會教你魔法Haunt（幽靈附體）作為回報的。輸入輸入文件ｄotr。in的第一行包含兩個整數Ｎ（1≤N≤51）和Ｍ（0≤M≤2,000）。分別表示裝備的種類數和金幣數。裝備用１到Ｎ的整數編號。接下來的N行，按照從裝備1到裝備N的順序，每行描述一種裝備.每一行的第一個正整數表示這個裝備貢獻的力量值。接下來的非空字符表示這種裝備是基本裝備還是高級裝備,Ａ表示高級裝備，B表示基本裝備。如果是基本裝備，緊接著的兩個正整數分別表示它的單價(單位為金幣）和數量限制(不超過1００）。如果是高級裝備,后面緊跟2Ｃ個數,表示合成這種裝備需要C種低級的裝備。第2I–1個數表示這個合成方案中第I種裝備的編號,第2I個數表示該裝備所需的個數。輸出請將輸出寫入ｄｏtr.oｕt。輸出文件的第一行包含一個整數S,表示最多可以提升多少點力量值。接下來的N行,每行一個整數,描述你提供的方案.第I行的整數表示你提供的方案中編號為I的裝備的購買數目.輸入數據保證正確的S不會超過2３1–1.如果有多種方案都能獲得最大的力量值,輸出任意一種即可。對于每個測試點，你的答案必須完全正確才能得分。樣例dotr.inｄoｔr.out１0595Ａ3６1921011B５31B４３1Ｂ２38A3２1317１１B535B3315A３11５１４1１Ｂ351B433300０22０0１００樣例說明裝備合成圖和問題描述中的圖相似.注意裝備1的合成需要兩個裝備9。112345678910*2題三巨額獎金Award/．IN／。OUT／．ＰAS/．EXE問題描述ＮJ市的快速發(fā)展得益于其便捷的交通?？墒?，隨著經濟的發(fā)展，大量的人進入NJ市,ＮJ市的交通也承受著巨大的壓力?，F在,NＪ市正在籌劃建設一個新型的交通樞紐,從而減輕交通的壓力.NＪ市包含n個區(qū)，有些區(qū)之間有雙向的干道存在。新型交通樞紐建設在這些干道的基礎上，將其中的部分干道改進為新型干道。改進后,干道能承受的壓力可以比原來增加幾十倍。為了和諧發(fā)展，在新型的交通樞紐建成后,要求任何兩個區(qū)之間都可以只通過新型干道（直接或間接地）連接。政府已經預測出每條干道改進為新型干道的費用.政府希望建設新型交通樞紐的總費用最小，并以巨額獎金向市民征集方案。政府很快發(fā)現費用最小的方案不一定唯一,所以決定將獎金平分給每一種方案的第一個設計者，即如果一個人設計的費用是最小的而且前面沒人和他設計出一模一樣的方案，則他可獲獎。Ｊs0８被獎金深深的吸引，準備設計一種方案?？墒?，他發(fā)現方案可能會很多，如果最后獲獎者太多，巨額的資金分到每個人頭上的也不會太多。所以他決定先算一下可行的方案數是多少.輸入輸入的第一行包含兩個數n（1≤n≤1０0）,m(1≤m≤１，０0０),分別表示該市有多少個區(qū)和有多少條干道。接下來m行，每行三個數ai、bｉ、ci（１≤ai,bi≤n,1≤ci≤１，000,