$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

1. 01分数规划问题基本上都可以用二分的方法来做
2. 点上的权值可以加到这个点的出边上
3. 我们只要判断出边 wf[i] - mid * wt[i] 是否存在正环
4. 易错点：dist[j] < dist[t] + wf[t] - mid * wt[i],是 wf[t],不是 wf[i],更新时亦如此

可参考： spfa判断负环

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1010, M = 5010;

int n,m;
int wf[N];
int h[N],e[M],wt[M],ne[M],idx;
double dist[N];
int cnt[N];
bool st[N];

void add(int a,int b,int c)
{
    e[idx]=b,wt[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

bool check(double mid)
{
    memset(cnt,0,sizeof cnt);
    memset(st,0,sizeof st);

    //把所有点都放进去
    queue<int> q;
    for(int i=1;i<=n;i++) 
    {
        q.push(i);
        st[i]=true;
    }

    while(q.size())
    {
        auto t=q.front();
        q.pop();
        st[t]=false;

        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];

            //把点上的权值加到它的出边上
            if(dist[j]<dist[t]+wf[t]-mid*wt[i])
            {
                dist[j]=dist[t]+wf[t]-mid*wt[i];
                cnt[j]=cnt[t]+1;

                //判定是否存在正环
                if(cnt[j]==n) return true;

                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }

    return false;
}

int main()
{
    cin>>n>>m;

    memset(h,-1,sizeof h);

    for(int i=1;i<=n;i++) cin>>wf[i];

    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }

    //二分查找答案
    double l=0,r=1000;
    while(r-l>1e-4)
    {
        double mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }

    printf("%.2lf\n",r);

    return 0;
}