题意：给定一张 n 个点、m 条边的有向图，每个点都有一个权值 f[i]，每条边都有一个权值 t[i]。
求图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大。
输出这个最大值。
思路：同样构造f(l), 令∑f[i] / ∑t[i] = l，那么∑f[i] = l*∑t[i] ，令f(l) = ∑(f[i] - l*t[i]) ,题目要求l尽可能大 ，也就是 ∑f[i] / ∑t[i] ≥ l 有更优解，也就是 f(l) ≥ 0 时有更优解，即∑(t[i]*l - f[i]) ≤ 0 有更优解，题目让求一个环，综上所述 如果存在更优解 说明这个图中存在负环，二分l ，通过是否存在负环判断边界
负环问题一般建议spfa来做，dalao: “spfa算法本身具有一个性质，就是在求解最短路的时候，是可以把点权和边权看做一个整体边权一起更新的，因此我们常常在一些spfa的图论问题中，把点权存入边权中进行计算。”
因此我们把边权换成t[i]*l - f[i]来存储，把每个点的权值存入他的出边中
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=2e5+7;
int f[N];
int head[N],e[N],ne[N],w[N],idx=0;
void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=head[a];
head[a]=idx++;
}
bool vis[N];
double dis[N];
int cnt[N],n,m;
int ok(double mid){
memset(vis,false,sizeof vis);
memset(cnt,0,sizeof cnt);
memset(dis,0,sizeof dis);
queue<int>q;
for(int i=1;i<=n;i++){
vis[i]=true;
q.push(i);
}
while(q.size()){
auto id=q.front();q.pop();
vis[id]=false;
for(int i=head[id];i!=-1;i=ne[i]){
int j=e[i];
double val=w[i]*mid-f[id];
if(dis[j]>dis[id]+val){
dis[j]=dis[id]+val;
cnt[j]=cnt[id]+1;
if(cnt[j]>=n) return true;
if(!vis[j]){
vis[j]=true;
q.push(j);
}
}
}
}
return false;
}
int main(){
memset(head,-1,sizeof head);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>f[i];
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
double l=1,r=1000;
while(r-l>1e-4){
double mid=(l+r)/2.;
if(ok(mid)) l=mid;
else r=mid;
}
printf("%.2lf\n",l);
return 0;
}