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不知道为啥,然后判断输出的最大值的时候忘记了要判断有没有⑨吧。。。
 

评论

0条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.