这道题是一道标准的01分数规划：
但是有一些细节可以优化：
不难想到要二分一个mid然后判定图上是否存在一个环S，该环是否满足∑i=1t(Fun[vi]−mid∗Tim[ei])>0
但是上面的算法并不好实现，所以可以将两边同时乘上-1,使式子变为∑i=1t(mid∗Tim[ei]−Fun[vi])<0
那么该问题就转化成了在每一个图中跑一边SPFA来寻找是否存在负环，若存在则l=mid，否则r=mid；
#include <bits/stdc++.h>
#define inc(a,b,c) for(register int i=a;i<=b;i+=c)
#define ini 20010
using namespace std;
int n,m;
struct littlestar{
int from;
int to;
int nxt;
double w;
}star[ini],star2[ini];
int head[ini],cnt,head2[ini];
void add(int u,int v,int w)
{
star[++cnt].to=v;
star[cnt].nxt=head[u];
star[cnt].from=u;
star[cnt].w=w;
head[u]=cnt;
}
int c[ini];
queue<int> q;
double dis[ini];
int vis[ini];
int SPFA()
{
int tot=;
for(int i=;i<=n;i++){
q.push(i);
dis[i]=;
vis[i]=;
}
while(q.size()){
int u=q.front();
q.pop();
vis[u]=;
for(int i=head2[u];i;i=star2[i].nxt){
int v=star2[i].to;
if(dis[v]>dis[u]+star2[i].w){
dis[v]=dis[u]+star2[i].w;
if(vis[v]==){
vis[v]=;
q.push(v);
++tot;
if(tot>*(n+m)) return ;
}
}
}
}
return ;
}
int check(double x)
{
inc(,cnt,){
star2[i]=star[i];
star2[i].w=(double)star[i].w*(double)x-(double)c[star[i].from];
}
inc(,n,){
head2[i]=head[i];
}
if(SPFA()){
return ;
}
else{
return ;
}
}
int read()
{
int x=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
}
int main()
{
n=read();
m=read();
inc(,n,) c[i]=read();
inc(,m,){
int u,v,w;
u=read();v=read();w=read();
add(u,v,w);
}
double l=0.00,r=1000010.000,mid;
while(r-l>1e-){
mid=(l+r)/;
if(check(mid)){
l=mid;
}
else{
r=mid;
}
}
printf("%.2lf",l);
}