noip常用算法

《noip常用算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.Dijkstra1)适用条件&范围：a)单源最短路径(从源点s到其它所有顶点v);b)有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图)c)所有边权非负(任取(i,j)∈E都有Wij≥0);2)算法描述：a)初始化：dis[v]=maxint(v∈V,v≠s);dis[s]=0;pre[s]=s;S={s};b)Fori:=1tonBegin取V-S中的一顶点u使得dis[u]=min{dis[v]

2、v∈V-S}S=S+{u}ForV-S中每个顶点vdoRelax(u,v,Wu,v)End;c)算法结束：dis[i]为s到i的

3、最短距离；pre[i]为i的前驱节点3)算法优化：使用二叉堆(BinaryHeap)来实现每步的DeleteMin(ExtractMin，即算法步骤b中第1步)操作，算法复杂度从O(V^2)降到O((V+E)㏒V)。推荐对稀疏图使用。使用FibonacciHeap(或其他Decrease操作O(1),DeleteMin操作O(logn)的数据结构)可以将复杂度降到O(E+V㏒V)；如果边权值均为不大于C的正整数，则使用RadixHeap可以达到O(E+V㏒C)。但因为它们编程复杂度太高，不推荐在信息学竞赛中使用。注：程序使用二叉堆4)程序：PROGRAM

4、DIJKSTRA;CONSTNUM=10;MAX=10000;TYPEGRP=ARRAY[1..NUM,1..NUM]OFINTEGER;RCD=SETOF1..NUM;ARR=ARRAY[1..NUM]OFINTEGER;ARR2=ARRAY[1..NUM]OFRCD;VARI,J,W,M,N,E,K:INTEGER;G:GRP;VISITED:ARRAY[1..NUM]OFBOOLEAN;PATH:ARR2;DIST,S:ARR;PROCEDURECREATEMTX;VARI,J,K:INTEGER;BEGINFORI:=1TONDOFORJ:=1T

5、ONDOG[I,J]:=MAX;FORK:=1TOEDOBEGINREADLN(I,J,W);G[I,J]:=W;G[J,I]:=W;END;END;PROCEDUREPRINT(G:GRP);BEGINFORI:=1TONDOBEGINFORJ:=1TONDOIFG[I,J]=MAXTHENWRITE('OO':4)ELSEWRITE(G[I,J]:4);WRITELN;END;END;PROCEDUREDIJKSTRA(VARDIST:ARR;VARPATH:ARR2;I:INTEGER);BEGINE:=I;FORJ:=1TONDOBEGINIFJ

6、<>ITHENS[J]:=0ELSES[J]:=1;DIST[J]:=G[I,J];IFDIST[J]ITHENS[M]:=1ELSEEXIT;FORJ:=1TONDOIF(S[J]=0)AND(DIST[M]+G[M,J]

7、J]:=DIST[M]+G[M,J];PATH[J]:=PATH[M]+[J];END;END;FORI:=1TONDOIFI<>ETHENBEGINFORJ:=1TONDOIFJINPATH[I]THENWRITE(J:3);WRITELN('W=':4,DIST[I]);END;END;BEGINASSIGN(INPUT,'DIJKSTRA.IN');ASSIGN(OUTPUT,'DIJKSTRA.OUT');RESET(INPUT);REWRITE(OUTPUT);READLN(N,E);CREATEMTX;WRITELN;READLN(I);DI

8、JKSTRA(DIST,PATH,I);WRITELN;CLOSE(INPUT);CLOSE(OUTPUT);END.2.Floyd-Warshall1)适用范围：a)APSP(AllPairsShortestPaths)b)稠密图效果最佳c)边权可正可负2)算法描述：a)初始化：dis[u,v]=w[u,v]b)Fork:=1tonFori:=1tonForj:=1tonIfdis[i,j]>dis[i,k]+dis[k,j]ThenDis[I,j]:=dis[I,k]+dis[k,j];c)算法结束：dis即为所有点对的最短路径矩阵3)算法小结：此算

9、法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行

10、V

11、次Dijkst