题目转换成求最小的一个环内边权和除以环内点的数量的值 可以用 0/1分数规划，每一个点：a[i]/b[i]<L = a[i]-L*b[i]<0 由于b[i]等于 1 (这个点)，所以简化成 a[i]-L 具体的看代码，注意变量使用的类型

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, double> PII; 
const int N=3010;
vector<PII> G[N];
int n, m, f[N], dd[N], vis[N]; double d[N];
bool check(double mid) 
{
    queue<int> q;
    for(int i=1; i<=n; ++i) vis[i]=1, d[i]=dd[i]=0, q.push(i);
    while(!q.empty()) 
    {
        int x=q.front(); q.pop(); vis[x]=0;
        for(auto i: G[x])
        {
            int y=i.first; double w=i.second - mid;
            if(d[y] > d[x] + w) 
            {
                d[y] = d[x] + w;
                dd[y] = dd[x] + 1; if(dd[y] > n) return true;
                if(!vis[y]) q.push(y), vis[y]=1;
            }
        }
    }
    return false;
}
int main() 
{
    scanf("%d%d", &n, &m);
    double w;
    for(int i=1, x, y; i<=m; ++i) scanf("%d%d%lf", &x, &y, &w), G[x].emplace_back(PII(y, w));
    double l=-1e7, r=1e7, eps=1e-10;// 最好用 1e7 (别的会错)
    while(r - l > eps)
    {
        double mid=(l + r)/2;
        if(check(mid)) r=mid;//有负环，就让答案变小 (题目求最小值)
        else l=mid;
    }
    printf("%.8lf\n", l);
    return 0;
}

/*
题目转换成求最小的一个环内边权和除以环内点的数量的值
可以用 0/1分数规划，每一个点：a[i]/b[i]<L = a[i]-L*b[i]<0
由于b[i]等于 1 (这个点)，所以简化成 a[i]-L
具体的看代码，注意变量使用的类型 
*/
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,double> PII; 
const int N=3010;
vector<PII>G[N];
int n,m,f[N],dd[N],vis[N];double d[N];
bool check(double mid) 
{
    queue<int>q;
    for(int i=1;i<=n;++i)vis[i]=1,d[i]=dd[i]=0, q.push(i);
    while(!q.empty()) 
	{
        int x=q.front();q.pop();vis[x]=0;
        for(auto i:G[x])
		{
            int y=i.first;double w=i.second-mid;
            if(d[y]>d[x]+w) 
			{
                d[y]=d[x]+w;
                dd[y]=dd[x]+1;if(dd[y]>n) return True;
                if(!vis[y]) q.push(y),vis[y]=1;
            }
        }
    }
    return False;
}
int main() 
{
    scanf("%d%d",&n,&m);
    double w;
    for(int i=1,x,y;i<=m;++i)scanf("%d%d%lf",&x,&y,&w),G[x].emplace_back(PII(y,w));
    double l=-1e7,r=1e7,eps=1e-10;// 最好用 1e7 (别的会错)
    while(r-l>eps)
	{
        double mid=(l+r)/2;
        if(check(mid))r=mid;//有负环，就让答案变小 (题目求最小值)
        else l=mid;
    }
    printf("%.8lf\n",l);
    return 0;
}