O(NVE)Bellman-ford，判断每个农场是否存在负权环，如果有，就能遇到未来的自己。const maxn=5000; maxe=10000000;type edge=record a,b,w:longint;end;var edges:array[1..maxe]of edge; dis:array[1..maxn]of longint; PRe:array[1..maxn]of longint; e,n,s,t:longint;procedure init;var x,y,z,i,j:longint;begin readln(n,s,t); for i:=1 to s do begin readln(x,y,z); with edges[i*2-1] do begin a:=x;b:=y;w:=z;end; with edges[i*2] do begin a:=y;b:=x;w:=z;end; end; e:=s*2; for i:=1 to t do begin readln(x,y,z); with edges[i+e] do begin a:=x;b:=y;w:=-z;end; end; e:=e+t; fillchar(dis,sizeof(dis),$7f div 3); dis[s]:=0;pre[s]:=s;end;procedure relax(u,v,w:integer);begin if dis[u]+w<dis[v] then begin dis[v]:=dis[u]+w; pre[v]:=u; endend;function bellman_ford:boolean;var i,j:longint;begin for i:=1 to n do for j:=1 to e do with edges[j] do relax(a,b,w); for i:=1 to e do with edges[i] do if dis[a]+w<dis[b] then exit(false); exit(true)end;var i,o:longint;begin readln(o); for i:=1 to o do begin init; if bellman_ford then writeln('No') else writeln('Yes') end;end.
