2005acm杯比赛往年试题集锦

《2005acm杯比赛往年试题集锦》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、ConstructingRoadsTimeLimit:2000MSMemoryLimit:65536KTotalSubmissions:12262Accepted:4862DescriptionThereareNvillages,whicharenumberedfrom1toN,andyoushouldbuildsomeroadssuchthateverytwovillagescanconnecttoeachother.WesaytwovillageAandBareconnected,ifandonlyifthereisaroadbetweenAandB,orthereexistsavil

2、lageCsuchthatthereisaroadbetweenAandC,andCandBareconnected.Weknowthattherearealreadysomeroadsbetweensomevillagesandyourjobisthebuildsomeroadssuchthatallthevillagesareconnectandthelengthofalltheroadsbuiltisminimum.InputThefirstlineisanintegerN(3<=N<=100),whichisthenumberofvillages.ThencomeNlines,th

3、ei-thofwhichcontainsNintegers,andthej-thoftheseNintegersisthedistance(thedistanceshouldbeanintegerwithin[],1000])betweenvillageiandvillagej・ThenthereisanintegerQ(0<=Q<=N*(N+1)/2).ThencomeQlines,eachlinecontainstwointegersaandb(1<=a

4、utYoushouldoutputalinecontainsaninteger,whichisthelengthofalltheroadstobebuiltsuchthatallthevillagesareconnected,andthisvalueisminimum.SampleInput3099069299001796921790112SampleOutput179SourcePKUMonthly,kiccTheWolvesandtheSheepTimeLimit:15000MSMemoryLimit:131072KTotalSubmissions:332Accepted:77Desc

5、riptionNalim,OcisandRemmargutsareplayingongrass,andtheyfeelveryhungrynow.Asbabywolves,theydecidetocapturealittlesheeptoeat.Fortunately,theyimmediatelydiscoverasheeproamingaroundthegrass.However,whattheyfoundisthequeenofthesheep——Mmxl,whohasextraordinaryspeedthatcancomparewiththewolves,andisverycle

6、ver!CanyoujudgewhetherthebabywolveswillcaptureMmxl!Therearesomerulestofollow:ThegrassfieldisarectangularareathatconsistofR*Cgrids.Andsomeobstacleslikestonesortreesexist.TheactionsofthebabywolvesandMmxlaretakeninrounds.Ineachround,babywolvestakeactionsfirst,andthenMmxlfollows.Inthebabywolves1turn,t

7、hethreewolveswillmakeadecision,andchooseoneofthemtomove(amovemeansmovingfromagridtoaneighboringgrid).Theremustbeawolftomove,unlessnoneofthemcanmove.IntheMmxfsturn,shewillalwaysmove.Ifshecannotmove,sheiscaptured.B