对于求分数的最小值 , $\frac{\Sigma w_i}{\Sigma num_i}<=mid$我们二分这个$mid$然后如果存在负环说明$ans<mid$那么$r=mid$如果不存在负环那么说明$ans>=mid$此时令$l=mid$我们发现唯一一个$mid$可以和$ans$取到的地方在$l$那里 , 所以最后的答案要输出$l$ , 这是由于我们的目标式子是$<=$然而负环是$<$不一样 , 所以不是if(ck(mid)) r=mid,ans=mid此时的$ans$也就是$r$根本就不是答案 , 这就是为什么https://www.udebug.com/UVa/11090 的第一个测试样例97点的391.62会变成391.63的原因 , 放一下我的代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pb push_back
#define db double
#define lowbit(x) x&(-x)
#define cerr(x) cerr<<#x<<"="<<x<<endl
#define endl '\n'
template<typename T>
void maxx(T &x,T y) {x=max(x,y);}
template<typename T>
void minn(T &x,T y) {x=min(x,y);}
#define N 55
typedef pair<int,db> pr;
const db eps=1e-8;
int n,m;
db dis[N],backup[N];
bool in[N],vis[N];
int tot[N];
struct node{int x,y;db z;};
vector<node>pre;
vector<pr>g[N];
vector<int>h[N];
int cmp(db x,db y) {
    if(fabs(x-y)<eps) return 0;
    if(x>y) return 1;
    return -1;
}
void add(int a,int b,db c) {g[a].pb({b,c});}
void init() {
    for(int i=0;i<=n;i++) dis[i]=1e9;
    for(int i=0;i<=n;i++) backup[i]=1e9;
    for(int i=0;i<=n;i++) tot[i]=0;
    for(int i=0;i<=n;i++) vis[i]=0;
    for(int i=0;i<=n;i++) in[i]=0;
}
bool spfa(int s,db mid) {
    queue<int>q;
    dis[s]=0;
    in[s]=1;
    tot[s]=1;
    q.push(s);
    while(q.size()) {
        int now=q.front();q.pop();
        if(!in[now]) continue;
        in[now]=0;
        vis[now]=1;
        for(auto [v,w]:g[now]) {
            if(cmp(dis[now]+w-mid,dis[v])==-1) { 
                dis[v]=dis[now]+w-mid;
                tot[v]=tot[now]+1;
                if(tot[v]>n) return 1;//存在负环
                if(!in[v]) {
                    in[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return 0;
}
// bool bellman_ford(db mid) {
//     dis[1]=0;
//     for(int i=1;i<=n;i++) {
//         memcpy(backup,dis,sizeof(dis));
//         for(auto v:pre) {
//             auto [x,y,z]=v;z-=mid;
//             if(cmp(backup[x]+z,dis[y])==-1) {
//                 if(i==n) return 1;
//                 dis[y]=backup[x]+z;
//             }
//         }
//     }
//     return 0;//一直在这里,没有负环
// }
bool ck(db mid) {
    init();
    // return bellman_ford(mid);
    for(int i=0;i<=n;i++) vis[i]=0;
    bool flag=0;
    for(int i=1;i<=n;i++) {
        if(vis[i]) continue;
        flag |= spfa(i,mid);
    }
    return flag;
}//存在负环就是满足条件
int test=0;
void solve() {
    cin>>n>>m;//如果点的下标出现0那么循环枚举的也要从0开始
    pre.clear();
    for(int i=1;i<=n;i++) g[i].clear();
    for(int i=0;i<m;i++) {
        int x,y;db z;cin>>x>>y>>z;
        pre.pb({x,y,z});
        add(x,y,z);
    }
    db l=0,r=1e9,mid;
    while(r-l>eps) {
        mid=(l+r)/2;
        if(ck(mid)) r=mid;//存在负环
        else l=mid;
    }
    cout<<"Case #"<<++test<<": ";
    if(cmp(l,1e9)==0) {cout<<"No cycle found."<<endl;return;}
    cout<<fixed<<setprecision(2)<<l<<endl;//答案在l中不是在r中
}
int main() {
    // freopen("E:\\Edit\\1.txt","r",stdin);
    // freopen("E:\\Edit\\output.txt","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) 
    solve();
    return 0;
}