前向星+SPFA.docxVIP

我是在做USACO的sweet butter时偶然发现这个东西的。。。这个算法，简单的说就是队列优化的bellman-ford,利用了每个点不会更新次数太多的特点发明的此算法（仅为个人理解=.=）SPFA——Shortest Path Faster Algorithm，它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。SPFA的实现甚至比Dijkstra或者Bellman_Ford还要简单：设Dist代表S到I点的当前最短距离，Fa代表S到I的当前最短路径中I点之前的一个点的编号。开始时Dist全部为+∞，只有Dist[S]=0，Fa全部为0。维护一个队列，里面存放所有需要进行迭代的点。初始时队列中只有一个点S。用一个布尔数组记录每个点是否处在队列中。每次迭代，取出队头的点v，依次枚举从v出发的边v-u，设边的长度为len，判断Dist[v]+len是否小于Dist，若小于则改进Dist，将Fa记为v，并且由于S到u的最短距离变小了，有可能u可以改进其它的点，所以若u不在队列中，就将它放入队尾。这样一直迭代下去直到队列变空，也就是S到所有的最短距离都确定下来，结束算法。SPFA 在形式上和宽度优先有哪些信誉好的足球投注网站非常类似，不同的是宽度优先有哪些信誉好的足球投注网站中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k，有办法证明对于通常的情况，k在2左右前向星优化：不要把前向星想成什么高深莫测的东西……它其实就是一种邻接表的紧缩存储形式。为什么叫前向星？因为它是将边按照前端点排序，并用一个数组k[i]记录端点i第一次以左端点出现的位置。这样，我们就能用O(E)的空间复杂度存储下一个邻接表，而避免了链表或N^2的庞大空间消耗。当然，实际上我们并不需要排序：因为我们只需要知道某一条边应该放到什么位置即可。因而我们还需要一个数组t[i]存储从i出发的边的条数。则需要存储在的位置就可以很轻易地求得。（详见代码）Butter题目代码如下：Program butter(input,output);Type?? edge=record??????????? x,y,d:longint;??????? end;Var?? min,res,n,p,c,x,y,i,j,l,r:longint;?? te,e:array[0..3000] of edge;?? tk,t,k,num,d:array[1..800] of longint;?? q:array[1..100000] of longint;?? use:array[1..800] of boolean;Procedure swap(var n1,n2:longint);Var?? tmp:longint;Begin?? tmp:=n1;n1:=n2;n2:=tmp;End;Begin?? assign(input,butter.in);reset(input);?? readln(n,p,c);?? for i:=1 to n do?? begin????? read(x);????? inc(num[x]);?? end;?? for i:=1 to c do?? begin????? with e[i*2-1] do readln(x,y,d);????? e[i*2]:=e[i*2-1];????? swap(e[i*2].x,e[i*2].y);?? end;?? c:=c*2;?? for i:=1 to c do inc(t[e[i].x]);?? j:=0;k[1]:=1;?? for i:=2 to p do????? k[i]:=k[i-1]+t[i-1];?? tk:=k;te:=e;?? for i:=1 to c do?? begin????? e[tk[te[i].x]]:=te[i];????? inc(tk[te[i].x]);?? end;?? min:=maxlongint;?? for i:=1 to p do?? begin????? fillchar(q,sizeof(q),0);????? fillchar(d,sizeof(d),127);????? fillchar(use,sizeof(use),false);????? q[1]:=i;l:=1;r:=1;d[i]:=0;use[i]:=true;????? repeat??????????? for j:=k[q[l]] to k[q[l]]+t[q[l]]-1 do?????????????? if d