图论类型各题总结acm

《图论类型各题总结acm》由会员分享，可在线阅读，更多相关《图论类型各题总结acm（38页珍藏版）》请在装配图网上搜索。

1、hdu4318 Power transmission 最短路 当数据很大的时候的解决办法 一道题目的解题全过程记录最短路 解决大数据模拟链表Power transmissionTime Limit： 10000/5000 MS （Java/Others) Memory Limit： 131072/131072 K (Java/Others）Total Submission(s)： 663 Accepted Submission(s）： 231Problem DescriptionThe project WestEast power transmission is famous around t

2、he world。 It transmits the electricity from western areas to east China. There are many nodes in the power system。 Each node is connected with several other nodes in the system by cable。 Power can be only transmitted between two connected nodes。 For each node， it cant send power to two or more other

3、 nodes at the same time。As we have all known， power will be loss during the transmission。 Bob is the chief engineer of the project。 He wants to build a transmission line which send power from one node to another node and minimize the power loss at the same time。 Now he asks you to help him solve the

4、 problem。 InputThere are several test cases. For each test case， the first line contains an integer N （0 N 50000） which represents the number of nodes in the power system。 Then there will be N groups of data following。 For the i-th（0 i N) group, the first line is an integer ki (ki 50)， which means t

5、he node i is connected with ki nodes. The rest of the ith group data are divided into ki lines. Each line contains an integer ai (0 2 4， loss power is 100 50 + 100 * (100-50）20 = 60.00MicrosoftInternetExplorer402DocumentNotSpecified7。8Normal0题意:多个点 从一个点往另一个点运输天然气 但是从某点到另外一点是会有损耗的 题中输入的即为损耗的百分数 问从点s到

6、t最少损耗多少 分析： 很明显是最短路问题 但是有个比较卡人的地方 就是最多会有50000个点 数据太大 用map数组存不下 会爆掉 我们考虑到用链表 就用了数组去模拟链表 保存从当前点能到达的点队长把写解题报告的任务光荣的交给了我 但是我对看代码表示相当的纠结 所以就自己去写了个 好理解 把自己的贴上 /#includestdio。hincludestruct hahaint son55; /记录从当前点到其它能走到的点double son_val55； /记录从当前点到其它能走到的点的消耗int cnt；/记录存取的儿子个数a50100；int n，flag，s，t,M,used50100

7、；double min50100；double find_short（)/模拟以前数据比较小的时候的模板 int i,j，pos,cnt； double mm； memset（used,0,sizeof（used）; for(i=1；i=n;i+） mini=1; cnt=t； while（cnt) minas。soncnt=as。son_valcnt； useds=1； mins=0； for（i=2;i=n;i+) mm=1； for（j=1;j=n;j+） if（！usedjmmminj) pos=j； mm=minj; if（mm=1) flag=1；return 0； usedpos

8、=1; cnt=apos。cnt； for（j=0；jcnt；j+) if（！usedapos。sonj&minpos+（1。0-minpos)*apos.son_valjminapos.sonj） minapos。sonj=minpos+(1.0minpos）apos。son_valj; if（pos=t） return mint；/这里很重要 不加会超时的哦 return mint;int main(）int i,m，x，y；double val,k；while（scanf（d，n）！=EOF）flag=0；for（i=1；i=n;i+） ai。cnt=0；for(i=1；i#includ

9、estring。hint n，used1005;double map10051005，min1005；void find_short（int s）int i，j,pos；double mm；memset（used,0,sizeof(used);for（i=1;i=n；i+）mini=mapsi;mins=1；useds=1；for（i=2；i=n；i+）pos=0;mm=-1；for(j=1;j=n；j+）if（！usedj&mmminj）pos=j；mm=minj;usedpos=1;if（mm=1) break；for(j=1;jminj）minj=minpos*mapposj;int m

10、ain（）int i,j，m，s，e;while（scanf(”d”，n)!=EOF）for（i=1;i=n;i+）for（j=1;jc1-.。.。ck-dTotal cost ： .。.。.。.From e to f ：Path： e-e1-。.。.。.。-ek-fTotal cost ： 。.。Note: if there are more minimal paths， output the lexically smallest one。 Print a blank line after each test case。 Sample Input50 3 22 -1 43 0 5 -1 12

11、2 5 0 9 20-1 1 9 0 44 1 20 4 05 17 8 3 11 33 52 41 10 Sample OutputFrom 1 to 3 ：Path: 154-3Total cost ： 21From 3 to 5 :Path: 3-4-5Total cost : 16From 2 to 4 ：Path： 2-1-5-4Total cost : 17#includestdio。hincludestring.h#define size 1000int valsize,mapsizesize,usedsize,minsize，n,startsize，endsize,flag，p

12、resize；char s11300,s21300；int ok（int n1，int n2,int s）/比较字典序大小int i,k; i=0； s1i+=n1+0； k=pren1; while(k！=s) s1i+=k+0；k=prek; s1i+=s+0； s1i=0; strrev（s1);/把字符串翻转过来 i=0； s2i+=n1+0; k=n2;/因为依然是n1(j）为最后一个 通过n2（pos)架桥 while(k!=s） s2i+=k+0；k=prek; s2i+=s+0; s2i=0； strrev(s2); if(strcmp(s2,s1）0）return 1； el

13、se return 0；void find_short(int s)int i，j，mm，pos；memset（used，0，sizeof（used）);for（i=1；i=n;i+）mini=mapsi；if（mapsi!=999999999） /这一步居然忘记了 阿弥陀佛 记住这个千万不能少prei=s；mins=0；useds=1；for（i=2；i=n;i+）mm=999999999;for（j=1；j=n;j+)if(!usedj&mmminj)pos=j；mm=minj；if(mm=999999999） break;usedpos=1；for(j=1;j=n;j+）if（!used

14、j&minpos+mapposj+valposminj）minj=minpos+mapposj+valpos；prej=pos;elseif（！usedjminpos+mapposj+valpos=minj）if（ok（j，pos，s） prej=pos；/如果pos之前的字典序较小那么更新void print(int s，int e)int asize，i，k；k=0;ak+=e；i=e；while(s！=i）i=prei；ak+=i；printf(”Path： ”);for(i=k1；i0；i）printf(”d-，ai）；printf(”dn，a0);int main（)int i，j,

15、s，e,num；while(scanf(”d”，&n）&n!=0)num=0；for(i=1；i=n；i+）for(j=1;j=n；j+)scanf（d”，mapij)；if(mapij=-1） mapij=999999999;for（i=1；i=n；i+）scanf(”d”，&vali)；while（1）scanf(%d d”，s,e）；if（s=1&e=1) break；startnum=s；endnum+=e;for（i=0;inum；i+)flag=0；find_short（starti)；printf(From d to d ：n”,starti，endi)；if（starti！=e

16、ndi）print(starti,endi)；else printf(”Path: dn”，starti）;printf(”Total cost : dn，minendi）；printf（”n”）;return 0；/*记录路径思路就是加入一个pre数组 时时更新每个点前面的点是什么 另外不要忘记从始点出发到i的所有的pre都要赋值初始点本题要求按字典序找出最短的路径 一开始我感到很恐惧 不知道怎么做 其实心里没有必要那么害怕 只要尝试着一点一点的去做不要不敢尝试就退却 把大问题分解成一个一个小问题 硬着头皮也要上 （看了别人代码才A了）/hdu1548 A strange lift 不错的变

17、相最短路考察分类: 图论 20120727 23：2412人阅读评论（0）收藏编辑删除A strange liftTime Limit: 2000/1000 MS （Java/Others） Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 5507 Accepted Submission（s)： 2009Problem DescriptionThere is a strange lift。The lift can stop can at every floor as you want， and there is a n

18、umber Ki(0 = Ki = N) on every floor。The lift have just two buttons： up and down.When you at floor i,if you press the button ”UP ， you will go up Ki floor,i.e，you will go to the i+Ki th floor，as the same, if you press the button ”DOWN” ， you will go down Ki floor，i。e,you will go to the i-Ki th floor。

19、 Of course, the lift cant go up high than N，and cant go down lower than 1. For example, there is a buliding with 5 floors, and k1 = 3, k2 = 3，k3 = 1，k4 = 2， k5 = 5。Begining from the 1 st floor,you can press the button ”UP”， and youll go up to the 4 th floor，and if you press the button DOWN”, the lif

20、t cant do it， because it cant go down to the -2 th floor，as you know ,the 2 th floor isnt exist.Here comes the problem: when you is on floor A，and you want to go to floor B，how many times at least he havt to press the button ”UP or ”DOWN”？ InputThe input consists of several test cases。,Each test cas

21、e contains two lines.The first line contains three integers N ,A，B（ 1 = N，A，B #includestring。hint map205205，used205,min205,n,start，end;void init(）int i，j;for(i=1;i=n；i+)for（j=1;j=n;j+） if（i！=j） mapij=999999999；else map00=0;void find_short(）int i，j,mm，pos；memset（used，0，sizeof(used)）；for(i=1;i=n；i+）mi

22、ni=mapstarti；minstart=0； usedstart=1;for（i=2;i=n；i+)pos=0；mm=999999999；for（j=1;j=n;j+）if（！usedjmmminj）pos=j；mm=minj；usedpos=1；if（mm=999999999） break；for（j=1；j=n;j+）if（！usedjminpos+mapposjminj）minj=minpos+mapposj；int main（）int i，d;while(scanf(”%d”，n)！=EOF)if(n=0） break；scanf(”d d,&start，&end）；init(）；

23、for（i=1;i=n；i+)scanf（”d”,d)；if（i-d=1） mapiid=1；if(i+d=n） mapii+d=1;find_short（)；if(minend=999999999） printf（”1n）；elseprintf（”dn，minend）;return 0;A Walk Through the ForestTime Limit: 2000/1000 MS （Java/Others） Memory Limit： 65536/32768 K （Java/Others)Total Submission（s）： 2963 Accepted Submission（s）：

24、1075Problem DescriptionJimmy experiences a lot of stress at work these days， especially since his accident made working difficult。 To relax after a hard day， he likes to walk home。 To make things even nicer, his office is on one side of a forest， and his house is on the other。 A nice walk through th

25、e forest， seeing the birds and chipmunks is quite enjoyable。The forest is beautiful， and Jimmy wants to take a different route everyday. He also wants to get home before dark， so he always takes a path to make progress towards his house。 He considers taking a path from A to B to be progress if there

26、 exists a route from B to his home that is shorter than any possible route from A. Calculate how many different routes through the forest Jimmy might take. InputInput contains several test cases followed by a line containing 0。 Jimmy has numbered each intersection or joining of paths starting with 1

27、. His office is numbered 1， and his house is numbered 2。 The first line of each test case gives the number of intersections N， 1 N 1000， and the number of paths M。 The following M lines each contain a pair of intersections a b and an integer distance 1 d 1000000 indicating a path of length d between

28、 intersection a and a different intersection b. Jimmy may walk a path any direction he chooses。 There is at most one path between any pair of intersections。 OutputFor each test case， output a single integer indicating the number of different routes through the forest。 You may assume that this number

29、 does not exceed 2147483647 Sample Input5 61 3 21 4 23 4 31 5 124 2 345 2 247 81 3 11 4 13 7 17 4 17 5 16 7 15 2 16 2 10 Sample Output24大致题意：他的办公室用1表示,家用2 表示,从1到2,中间可能会经过其它节点，而该节点可走的原则是：假设他此时在A处，B与其相邻，只有当B到2 路线中存在一条比A到2 的任意一条路径都短的路径，才能走B.问这样的路线有多少种？分析:对于题目中的原则我可以这样考虑,如果B到2 的最短路径都比A到2 的最短路径长，显然题目的条件是

30、不成立的，即B不能走。而如果B到2 的最短路径比A到2 的最短路径短,那么题目的条件是成立的,即这样的路线一定存在，路线长度也可能介于A，B分别到2 的最短路径长度之间.也就是说，我们需要求出每个点到2 的最短路径长度,然后按题目原则深搜,能搜出几条就是几条。includestdio。hincludestring。hint map10051005,used1005，min1005，m，n，ans，used21005，dp1005；void init()int i，j；for(i=1；i=n；i+)for(j=1；j=n；j+）if(i！=j) mapij=999999999;else mapi

31、j=0；void find_short(int s)int i，j,mm，pos； memset(used,0,sizeof(used）; for（i=1;i=n；i+）mini=mapsi; mins=0； useds=1； for（i=2;i=n；i+) mm=999999999；for（j=1;j=n；j+）if（!usedj&mmminj）pos=j；mm=minj;if(mm=999999999） break；usedpos=1;for（j=1;jmini）dpnum=dpnum+DFS(i）;return dpnum;int main(）int i，x,y，z；while（scan

32、f(d，&n)&n！=0)scanf(”d”,m)；init（）；for（i=1;i=m;i+）scanf（d d d”,x，y，z）；if（mapxyz） mapxy=mapyx=z;find_short（2）;memset(dp，-1，sizeof(dp）;ans=DFS(1）;printf（”%dn，ans)；return 0;/*参考了人家的代码才有了思路 /一个人的旅行Time Limit: 1000/1000 MS (Java/Others） Memory Limit: 32768/32768 K （Java/Others）Total Submission（s）： 8364 Acc

33、epted Submission(s）： 2863Problem Description虽然草儿是个路痴（就是在杭电待了一年多，居然还会在校园里迷路的人，汗），但是草儿仍然很喜 欢旅行，因为在旅途中 会遇见很多人(白马王子，0)，很多事,还能丰富自己的阅历，还可以看美丽的风景草儿想去很多地方,她想要去东京铁塔看夜景，去威尼斯看电影，去 阳明山上看海芋，去纽约纯粹看雪景，去巴黎喝咖啡写信，去北京探望孟姜女眼看寒假就快到了,这么一大段时间,可不能浪费啊，一定要给自己好好的放个 假，可是也不能荒废了训练啊，所以草儿决定在要在最短的时间去一个自己想去的地方！因为草儿的家在一个小镇上，没有火车经过,所以

34、她只能去邻近的城市坐火 车(好可怜啊）。 Input输入数据有多组，每组的第一行是三个整数T，S和D，表示有T条路，和草儿家相邻的城市的有S个，草儿想去的地方有D个;接着有T行，每行有三个整数a，b，time，表示a，b城市之间的车程是time小时；（1=(a,b)=1000;a，b 之间可能有多条路）接着的第T+1行有S个数,表示和草儿家相连的城市；接着的第T+2行有D个数，表示草儿想去地方. Output输出草儿能去某个喜欢的城市的最短时间。 Sample Input6 2 31 3 51 4 72 8 123 8 44 9 129 10 21 28 9 10 Sample Output9

35、#includestdio。hincludestring.hint map10051005，used1005，n，m，start1005，end1005，max,min1005;void init（） int i,j； for(i=1；i=1003；i+） for（j=1；j=1003；j+） if（i！=j） mapij=999999999; else mapij=0；void find_short(int s） int i,j，mm,pos； memset(used,0,sizeof（used)）； for(i=1;i=max；i+） mini=mapsi; mins=0； useds=1

36、； for（i=2;i=max;i+) mm=999999999; for（j=1；jmax） max=y; if(mapxyt） mapyx=mapxy=t；/一开始只是给mapxy赋了值 好二逼啊 WA了2次 for（i=1；i=startnum;i+) scanf(”d”,starti）; if(maxstarti） max=starti； for(i=1；i=endnum；i+） scanf(”%d”,endi); if(maxendi） max=endi; for(i=1;i=startnum；i+) find_short（starti）; for(j=1；j=endnum；j+)

37、if(ansminendj） ans=minendj； printf(”dn”，ans）； return 0；很好的双限制最短路之hdu3750 最短路径问题Time Limit： 2000/1000 MS （Java/Others） Memory Limit： 32768/32768 K (Java/Others)Total Submission（s）: 3675 Accepted Submission（s）: 1114Problem Description给你n个点，m条无向边,每条边都有长度d和花费p,给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出

38、花费最少的. Input输入n,m，点的编号是1n，然后是m行,每行4个数 a，b,d，p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s，t；起点s，终点。n和m为0时输入结束.（1n=1000， 0m100000， s != t) Output输出 一行有两个数， 最短距离及其花费。 Sample Input3 21 2 5 62 3 4 51 30 0 Sample Output9 11#includestdio。h#includestring。hint n，m,min1005，start，end，used1005，cost1005；struct haha int

39、value; int dis;map10051005;void init（） int i，j; for（i=1;i=n；i+) for（j=1;j=n;j+） if(i！=j） mapij。dis=999999999; mapij。value=999999999； else mapij.dis=0； mapij。value=0； void find_ans（） int i，j，mm，pos,v=0； memset（used，0，sizeof（used）)； for（i=1；i=n；i+) mini=mapstarti。dis； costi=mapstarti。value； minstart=0; coststart=0; usedstart=1； for（i=2;i=n；i+) mm=999999999； for（j=1；j=n;j+） if(！usedjmmminj）