2003年15届国际信息学奥赛试题

《2003年15届国际信息学奥赛试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2003年第15届国际信息学奥赛试题解析（美国）第一题兽径管理TrailMaintenance(interactivetask)TaskFarmerJohn’scowswishtotravelfreelyamongtheN(1<=N<=200)fields(numbered1…N)onthefarm,eventhoughthefieldsareseparatedbyforest.Thecowswishtomaintaintrailsbetweenpairsoffieldssothattheycantravelfromanyfieldtoanyotherf

2、ieldusingthemaintainedtrails.Cowsmaytravelalongamaintainedtrailineitherdirection.Thecowsdonotbuildtrails.Instead,theymaintainwildanimaltrailsthattheyhavediscovered.Onanyweek,theycanchoosetomaintainanyorallofthewildanimaltrailstheyknowabout.Alwayscurious,thecowsdiscoveronenewwilda

3、nimaltrailatthebeginningofeachweek.Theymustthendecidethesetoftrail,tomaintainforthatweeksothattheycantravelfromanyfieldtoanyotherfield.Cowscanonlyusetrailswhichtheyarecurrentlymaintaining.Thecowsalwayswanttominimizethetotallengthoftrailtheymustmaintain.Thecowscanchoosetomaintaina

4、nysubsetofthewildanimaltrailstheyknowabout,regardlessofwhichtrailsweremaintainedthepreviousweek.Wildanimaltrails(evenwhenmaintained)areneverstraight.Twotrailsthatconnectthesametwofieldsmighthavedifferentlengths.Whiletwotrailsmightcross,cowsaresofocused,theyrefusetoswitchtrailsexc

5、eptwhentheyareinafield.Atthebeginningofeachweek,thecowswilldescribethewildanimaltrailtheydiscovered.Yourprogrammustthenoutputtheminimumtotallengthoftrailthecowsmustmaintainthatweeksothattheycantravelfromanyfieldtoanyotherfield,ifthereexistssuchasetoftrails.Inputstandardinput●Thef

6、irstlineofinputcontainstwospace-separatedintegers,NandW.Wisthenumberofweekstheprogramwillcover(1<=W<=6000).24●Foreachweek,readasinglelinecontainingthewildanimaltrailthatwasdiscovered.Thislinecontainsthreespace-separatedintegers:theendpoints(fieldnumbers)andtheinteger—lengthofthat

7、trail(…10000).Nowildanimaltrailhasthesamefieldasbothofitsendpoints.OutputstandardoutputImmediatelyafteryourprogramlearnsaboutthenewlydiscoveredwildanimal-trail,itshouldoutputasinglelinewiththeminimumtotallengthoftrailthecowsmustmaintainsothattheycantravelfromanyfieldtoanyotherfie

8、ld.Ifnosetoftrailsallowsthecowstotravelf