题解 P2850 【[USACO06DEC]虫洞Wormholes】

kczno1 · 2016-10-01 17:06:17 · 题解

spfa用dfs会对一个非最优的状态进行较多的无用的搜索，所以比bfs慢一些。

但在判断负环时如果用bfs就不知道到这个点的路径，所以只有入队>n次才能判断，所以时间最差为O(n*m)

而用dfs就可以知道路径，所以一旦一个点两次出现就可判断，时间仍能保持O(k*m)。

var
 farm,n,m,w,f,o,i,num,x,y,len:longint;
 t,g:array[1..500] of longint;
 l:array[1..10000,1..3] of longint;
 ok:boolean;//1则找到负环了，直接退出
 ing:array[1..500] of boolean;

procedure jia(x,y,len:longint);//加一条x->y的边
begin
 inc(num);
 l[num,3]:=t[x];t[x]:=num;
 l[num,1]:=y;l[num,2]:=len;
end;

procedure spfa(x:longint);
var i:longint;
begin
 ing[x]:=true;//在路径上
 i:=t[x];
 while i<>0 do
 begin
  if g[x]+l[i,2]<g[l[i,1]] then
  begin
   if ing[l[i,1]] then begin ok:=true;break; end;

   g[l[i,1]]:=g[x]+l[i,2];
   spfa(l[i,1]);
   if ok then break;
  end;

  i:=l[i,3];
 end;
 ing[x]:=false;
end;

procedure try;
begin
  readln(n,m,w);

 num:=0;
 for i:=1 to n do t[i]:=0;

 for i:=1 to m do
 begin
  read(x,y,len);
  jia(x,y,len);
  jia(y,x,len);
 end;
 for i:=1 to w do
 begin
  read(x,y,len);
  jia(x,y,-len);
 end;

 for i:=1 to n do g[i]:=1<<29;ok:=false;

 for f:=1 to n do
 if g[f]=1<<29 then
 begin
  g[f]:=0;
  spfa(f);
  if ok then exit;
 end;

end;

begin 
 readln(farm);
 for o:=1 to farm do
 begin
  try;
  if ok then writeln('YES')
  else writeln('NO');
 end;
end.

之前a了后才发现出发点不一定在负环中，于是造了这个点。a了的人可以试试看，说不定会re

1 3 2 1 1 2 5 2 3 3 3 2 4