分析

根据题意，即求 $\frac{\sum f}{\sum w}$ 的最大值 $v$ 。

这种形式的问题被称为01分数规划，通常使用二分法来求解：

如果 $v>mid$ ，那么取二分区间的右边，否则取左边。

对 $v>mid$ 进行变换，得到

$\sum (f_i-mid*w_i)>0$

进而有 $ \sum (mid*w_i-f_i)<0 $

也就是转化为判断图中有没有负环，其中边权指的是 $ mid*w_i-f_i $ 。

接下来就是基本操作了。

#include<bits/stdc++.h>
using namespace std;

const int N=1005, M=5005;
const double eps=1e-6;

struct node{
    int next,to,w;
}e[M<<1];
int head[N],tot;
void add(int u,int v,int w){e[tot].to=v, e[tot].next=head[u], e[tot].w=w, head[u]=tot++;}

int n,m;
int cnt[N];
double d[N];
bool vis[N];
double f[N];

bool check(double x){
    memset(vis,false,sizeof vis);
    memset(cnt,0,sizeof cnt);

    queue<int> q;
    for(int i=1;i<=n;i++){
        q.push(i);
        vis[i]=true;
    }   

    while(q.size()){
        int hd=q.front(); q.pop();

        vis[hd]=false;
        for(int i=head[hd];~i;i=e[i].next){
            int go=e[i].to;
            if(d[go]>d[hd]-f[hd]+x*e[i].w+eps){
                d[go]=d[hd]-f[hd]+x*e[i].w;
                cnt[go]=cnt[hd]+1;
                if(cnt[go]>=n) return true;

                if(!vis[go]){
                    vis[go]=true;
                    q.push(go);
                }
            }
        }
    }

    return false;
}

int main(){
    memset(head,-1,sizeof head);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>f[i];

    while(m--){
        int u,v,w; cin>>u>>v>>w;
        add(u,v,w);
    }

    double l=0, r=1e6;
    while(l+eps<r){
        double mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%.2lf\n",l);

    return 0;
}

upd on 2022/3/1:
新增了 dfs-spfa 的写法：

// Problem: 观光奶牛
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/363/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()

#define x first
#define y second
using pii = pair<int, int>;
using ll = long long;

inline void read(int &x){
    int s=0; x=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=1010, M=5050;
const double eps=1e-10;

int n, m;
int f[N];

struct Edge{
    int to, w, next;
}e[M];

int h[N], tot;

void add(int u, int v, int w){
    e[tot].to=v, e[tot].w=w, e[tot].next=h[u], h[u]=tot++;
}

bool vis[N];
double d[N];

bool spfa(int u, double x){
    vis[u]=true;
    for(int i=h[u]; ~i; i=e[i].next){
        int go=e[i].to;
        if(d[go]>d[u]+(e[i].w*x-f[go])){
            d[go]=d[u]+(e[i].w*x-f[go]);
            if(vis[go] || spfa(go, x)) return true;
        }
    }
    vis[u]=false;
    return false;
}

bool ok(double x){
    rep(i,1,n) vis[i]=d[i]=0;
    rep(i,1,n) if(spfa(i, x)) return true;
    return false;
}

int main(){
    memset(h, -1, sizeof h);
    cin>>n>>m;
    rep(i,1,n) read(f[i]);

    rep(i,1,m){
        int u, v, w; read(u), read(v), read(w);
        add(u, v, w);
    }   

    double l=0, r=1010;
    while(l+eps<r){
        double mid=(l+r)/2;
        if(ok(mid)) l=mid;
        else r=mid;
    }
    printf("%.2lf\n", l);

    return 0;
}