題意：f組數據，n個點，m條無向邊，w條有向負權邊，判斷是否有負權回路。
bellman-ford： 因為數組開小一直WA~ 1.做N次松弛操作，中間不能做就退出。 2.判斷當前解是否最優，不是最優就YES，否則NO。
時間復雜度:最優 O(KE) K是一個比N小很多的數 最壞O(NE)
var s,t,w,dis:array [0..5201] of longint; n,i,j,a,b,c,e:longint;function bellman_ford:boolean;var f,i,j:longint;begin for i:=1 to a do begin f:=0; for j:=1 to e do if dis[s[j]]+w[j]<dis[t[j]] then begin f:=1; dis[t[j]]:=dis[s[j]]+w[j]; end; if f=0 then break; end; for j:=1 to e do if dis[s[j]]+w[j]<dis[t[j]] then exit(true); exit(false);end;begin readln(n); for i:=1 to n do begin fillchar(dis,sizeof(dis),$7f); dis[1]:=0; e:=0; readln(a,b,c); for j:=1 to b do begin inc(e); readln(s[e],t[e],w[e]); s[e+1]:=t[e]; t[e+1]:=s[e]; w[e+1]:=w[e]; inc(e); end; for j:=1 to c do begin inc(e); readln(s[e],t[e],w[e]); w[e]:=0-w[e]; end; if bellman_ford then writeln('YES') else writeln('NO'); end;end.新聞熱點
疑難解答
