原题网址：http://www.lydsy.com/JudgeOnline/problem.php?id=1486 二分答案然后将所有边减去答案判有没有负环是比较容易想到的，关键是负环如果用一般的SPFA会T掉，这时候就要用到负环的一个性质：负环上必然存在一点使得从这点开始将边权按顺序相加的和始终为负。 所以可以dfs，一开始dis数组清零，因为扫到正的dis毫无用处，将每个点都dfs一遍（因为这个点不能确定究竟是哪个，要枚举）（途中dis不要清零，并且每个点都dfs过后dis数组表示的是第一个枚举的点到其他所有点的dis），途中如果发现dfs产生了环，就是有负环了。
const mxn=3001; eps=1e-10; type point=record y,next:longint; v:extended; end; var map:array[0..10001] of point; first:array[0..mxn] of longint; dis:array[0..mxn] of extended; vis:array[0..mxn] of boolean; n,e,s,x,y,i:longint; l,r,m,v:extended; flag:boolean; procedure ins(x,y:longint;v:extended); begin inc(s);map[s].y:=y;map[s].v:=v; map[s].next:=first[x];first[x]:=s; end; function dfs(x:longint):boolean; var t,y:longint; begin vis[x]:=true; t:=first[x]; while t>0 do begin y:=map[t].y; if dis[x]+map[t].v-m<dis[y] then begin dis[y]:=dis[x]+map[t].v-m; if (vis[y])or(dfs(y)) then exit(true); end; t:=map[t].next; end; vis[x]:=false; exit(false); end; function check:boolean; var i:longint; begin fillchar(vis,sizeof(vis),false); fillchar(dis,sizeof(dis),0); for i:=1 to n do if dfs(i) then exit(true); exit(false); end; begin read(n,e); fillchar(first,sizeof(first),0);s:=0; for i:=1 to e do begin read(x,y,v); ins(x,y,v); end; l:=-1e7;r:=1e7; repeat m:=(l+r)/2; if check then r:=m else l:=m; until l+eps>r; writeln(l:0:8); end.