图论类型各题总结材料-acm.doc

《图论类型各题总结材料-acm.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、hdu4318Powertransmission最短路当数据很大的时候的解决办法一道题目的解题全过程记录最短路解决大数据模拟链表PowertransmissionTimeLimit:10000/5000MS(Java/Others)MemoryLimit:131072/131072K(Java/Others)TotalSubmission(s):663AcceptedSubmission(s):231ProblemDescriptionTheprojectWest-Eastpowertransmissionisfamousaroundt

2、heworld.IttransmitstheelectricityfromwesternareastoeastChina.Therearemanynodesinthepowersystem.Eachnodeisconnectedwithseveralothernodesinthesystembycable.Powercanbeonlytransmittedbetweentwoconnectednodes.Foreachnode,itcan’tsendpowertotwoormoreothernodesatthesametime.Aswe

3、haveallknown,powerwillbelossduringthetransmission.Bobisthechiefengineeroftheproject.Hewantstobuildatransmissionlinewhichsendpowerfromonenodetoanothernodeandminimizethepowerlossatthesametime.Nowheasksyoutohelphimsolvetheproblem.InputThereareseveraltestcases.Foreachtestcas

4、e,thefirstlinecontainsanintegerN(0

5、s.Eachlinecontainsanintegerai(0

6、alpowerM(0

7、110440014100SampleOutput60.00HintInthesample,thebesttransmissionlineis1->2->4,losspoweris100*50%+100*(100%-50%)*20%=60.00MicrosoftInternetExplorer402DocumentNotSpecified7.8Normal0题意：多个点从一个点往另一个点运输天然气但是从某点到另外一点是会有损耗的题中输入的即为损耗的百分数问从点s到t最少损耗多少分析:很明显是最短路问题但是有个比较卡人的地方就是最多会有50

8、000个点数据太大用map数组存不下会爆掉我们考虑到用链表就用了数组去模拟链表保存从当前点能到达的点队长把写解题报告的任务光荣的交给了我但是我对看代码表示相当的纠结所以就自己去写了个好理解把自己的贴上/*#