bzoj1179:[Apio2009]Atm【tarjan+最短路径】
算是图论的比较简单的综合题目。
这怎么看都是单源点最长路啦~但由于路径会有环出现,所以我们就要先用tarjan缩点,这样处理后的图就是一个有向无环图,重新建图后用改造后的spfa就可以啦。
代码:
var a,next,v,low,dfn,w2,st,be,a2,next2,v2,dis,que:array[0..5000000]of longint; w:array[1..5000000]of integer; b,bar,bar2,inq:array[0..5000000]of boolean; n,m,i,j,k,p,q,s,t,head,tail:longint; procedure adde(uu,vv:longint); begin inc(k); v[k]:=vv; next[k]:=a[uu]; a[uu]:=k; end; procedure dfs(n:longint); var i:longint; begin inc(k); dfn[n]:=k; low[n]:=k; b[n]:=true; inc(st[0]); st[st[0]]:=n; i:=a[n]; while i<>0 do begin if dfn[v[i]]=0 then begin dfs(v[i]); if low[v[i]]<low[n] then low[n]:=low[v[i]]; end else if b[v[i]] and (dfn[v[i]]<low[n]) then low[n]:=dfn[v[i]]; i:=next[i]; end; if dfn[n]=low[n] then begin inc(t); repeat be[st[st[0]]]:=t; b[st[st[0]]]:=false; dec(st[0]); until st[st[0]+1]=n; end; end; procedure adde2(uu,vv:longint); begin inc(k); v2[k]:=vv; next2[k]:=a2[uu]; a2[uu]:=k; end; begin read(n,m); for i:=1 to m do begin read(p,q); adde(p,q); end; for i:=1 to n do read(w[i]); read(s,p); fillchar(bar,sizeof(bar),false); fillchar(bar2,sizeof(bar2),false); for i:=1 to p do begin read(q); bar[q]:=true; end; k:=0; fillchar(b,sizeof(b),false); for i:=1 to n do if be[i]=0 then dfs(i); k:=0; for i:=1 to n do begin j:=a[i]; while j<>0 do begin if be[v[j]]<>be[i] then adde2(be[i],be[v[j]]); j:=next[j]; end; inc(w2[be[i]],w[i]); if bar[i] then bar2[be[i]]:=true; end; fillchar(inq,sizeof(inq),false); head:=0; tail:=1; que[1]:=be[s]; inq[be[s]]:=true; dis[be[s]]:=w2[be[s]]; repeat inc(head); q:=que[head]; inq[q]:=false; i:=a2[q]; if head=500000 then head:=0; while i<>0 do begin if dis[q]+w2[v2[i]]>dis[v2[i]] then begin dis[v2[i]]:=dis[q]+w2[v2[i]]; if not inq[v2[i]] then begin inq[v2[i]]:=true; inc(tail); que[tail]:=v2[i]; if tail=500000 then tail:=0; end; end; i:=next2[i]; end; until head=tail; p:=0; for i:=1 to t do if (dis[i]>p) and bar2[i] then p:=dis[i]; writeln(p); end.
ps:一开始明明记得是五十万的数据范围结果弄成五百万了整天MLE不知道为啥,然后判断输出的最大值的时候忘记了要判断有没有⑨吧。。。
发表回复