// 二分+SPFA 算法 O(24*N*M)
#include<bits/stdc++.h>
using namespace std;

const int N=1010,M=5010;
int h[N],to[M],ww[M],ne[M],idx;
void add(int a,int b,int c){
  to[++idx]=b,ww[idx]=c,ne[idx]=h[a],h[a]=idx;
}
int n,m;
int f[N]; //点权
double d[N];
int cnt[N],vis[N];

bool spfa(double mid){
  memset(d,0,sizeof d);
  memset(vis,0,sizeof vis);
  memset(cnt,0,sizeof cnt);
  stack<int> q; //栈比队列快
  for(int i=1; i<=n; i++) q.push(i),vis[i]=true;
  
  while(!q.empty()){
    int u=q.top();q.pop();vis[u]=false;
    for(int i=h[u]; i; i=ne[i]){
      int v=to[i];
      double w=ww[i]*mid-f[u]; //等效边权
      if(d[v]>d[u]+w){
        d[v]=d[u]+w;
        cnt[v]=cnt[u]+1;
        if(cnt[v]>=n) return true; //有负环
        if(!vis[v]) q.push(v),vis[v]=true;
      }
    }
  }
  return false;
}
int main(){
  cin>>n>>m;
  for(int i=1; i<=n; i++) cin>>f[i]; //点权
  for(int i=0,a,b,c; i<m; i++){
    cin>>a>>b>>c;
    add(a,b,c);
  }
  
  double l=0,r=1000;
  while(r-l>1e-4){
    double mid=(l+r)/2;
    if(spfa(mid)) l=mid;
    else r=mid;
  }
  printf("%.2lf\n",r);
}

01规划

设答案为 ans。 二分答案，设当前二分值为 mid 设一个环 S的边权为 w1,w2,w3....点权为f1,f2,f3.... 若mid < ans，即存在一个环S使得 mid < ∑fi/∑wi,变换一下∑(mid*wi-fi) <0 否则，则mid > ans 每次 check 的时候，一条x指向y边权为w的边权变为:w * mid -fx。 我们只需检查这个图是否存在负环即可。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII; 
const int N=1010;
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 - f[x];
            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);
    for(int i=1;i<=n;++i) scanf("%d", &f[i]);
    for(int i=1, x, y, w;i<=m;++i) scanf("%d%d%d", &x, &y, &w), G[x].emplace_back(PII(y, w));
    double l=0, r=1000, eps=1e-4;
    while(r - l > eps)
	{
        double mid=(l + r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%.2lf\n", r);
    return 0;
}