裸题...平均权值最小的环....
注意$dfs-spfa$时$dfs(cl)$...不要写成$dfs(u)$
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; typedef long long ll; const int N=3005,M=1e4+5; const double eps=1e-9; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,m,u,v; double w; struct edge{ int v,ne; double w; }e[M]; int h[N],cnt=0; inline void ins(int u,int v,double w){ cnt++; e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt; } double d[N],g; int vis[N],cl; bool dfs(int u){ vis[u]=cl; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v;double w=e[i].w-g; if(d[v]>d[u]+w){ d[v]=d[u]+w; if(vis[u]==vis[v]) return true; else if(dfs(v)) return true; } } vis[u]=0; return false; } bool NegativeCircle(double mid){ g=mid; memset(vis,0,sizeof(vis)); memset(d,0,sizeof(d)); for(cl=1;cl<=n;cl++) if(dfs(cl)) return true; return false; } bool check(double mid){return NegativeCircle(mid);} void solve(){ double l=-1e7,r=1e7; while(r-l>eps){ double mid=(l+r)/2.0; if(check(mid)) r=mid; else l=mid; } printf("%.8lf",l); } int main(){ freopen("in","r",stdin); n=read();m=read(); for(int i=1;i<=m;i++){ u=read(),v=read(); scanf("%lf",&w); ins(u,v,w); } solve(); }