图论补充习题.doc

《图论补充习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、NKOJ1039:ArbitrageTimeLimit:1500ms  MemoryLimit:10000kB  TotalSubmit:56 (25users)   AcceptedSubmit:29 (24users)   PageView:1456 FontStyle:AaAaAaArbitrageistheuseofdiscrepanciesincurrencyexchangeratestotransformoneunitofacurrencyintomorethanoneunitofthesamecurrency.Forexam

2、ple,supposethat1USDollarbuys0.5Britishpound,1Britishpoundbuys10.0Frenchfrancs,and1Frenchfrancbuys0.21USdollar.Then,byconvertingcurrencies,aclevertradercanstartwith1USdollarandbuy0.5*10.0*0.21=1.05USdollars,makingaprofitof5percent.Yourjobistowriteaprogramthattakesalistofcu

3、rrencyexchangeratesasinputandthendetermineswhetherarbitrageispossibleornot.InputTheinputfilewillcontainoneormoretestcases.Omthefirstlineofeachtestcasethereisanintegern(1<=n<=30),representingthenumberofdifferentcurrencies.Thenextnlineseachcontainthenameofonecurrency.Within

4、anamenospaceswillappear.Thenextlinecontainsoneintegerm,representingthelengthofthetabletofollow.Thelastmlineseachcontainthenameciofasourcecurrency,arealnumberrijwhichrepresentstheexchangeratefromcitocjandanamecjofthedestinationcurrency.Exchangeswhichdonotappearinthetablear

5、eimpossible.Testcasesareseparatedfromeachotherbyablankline.Inputisterminatedbyavalueofzero(0)forn.OutputForeachtestcase,printonelinetellingwhetherarbitrageispossibleornotintheformat"Casecase:Yes"respectively"Casecase:No".SampleInput3USDollarBritishPoundFrenchFranc3USDolla

6、r0.5BritishPoundBritishPound10.0FrenchFrancFrenchFranc0.21USDollar3USDollarBritishPoundFrenchFranc6USDollar0.5BritishPoundUSDollar4.9FrenchFrancBritishPound10.0FrenchFrancBritishPound1.99USDollarFrenchFranc0.09BritishPoundFrenchFranc0.19USDollar0SampleOutputCase1:YesCase2

7、:NoNKOJ1784:SixDegreesofCowvinBaconTimeLimit:1500ms  MemoryLimit:65536kB  Judgetype:Multi-casesTotalSubmit:28 (15users)   AcceptedSubmit:15 (14users)   PageView:433 FontStyle:AaAaAaThecowshavebeenmakingmovieslately,sotheyarereadytoplayavariantofthefamousgame"SixDegreesofK

8、evinBacon".Thegameworkslikethis:eachcowisconsideredtobezerodegreesofseparation(degrees)awayfromh