题意：给出一个有向图，问求一个回路，使得回路上的点权之和/边权之和最大。

这题主要是分析出如何确定ans值。我们将(a1*x1+a2*x2+..+an*xn)/(b1*x1+b2*x2+..+bn*xn)=L，转换为：x1*(a1-b1*L)+x2*(a2-b2*L)+...xn*(an-bn*L)=0

则每次枚举L的值，spfa中边权值为len[]*L-a[]，若存在负环回路(即一个点访问次数超过n次)则表示L的值小了，增大L值;反之减小L值.

代码：

#include<iostream>

#include<cstring>

#include<cstdio>

#define MAXN 1052

#define inf 10000000

using namespace std;

struct Edge{

    int u,len,next;

}edge[5*MAXN];

int temp,n,m;

int head[MAXN],a[MAXN];

void addEdge(int u,int v,int c)

{

    edge[temp].u=v;

    edge[temp].len=c;

    edge[temp].next=head[u];

    head[u]=temp;

    temp++;

}

double dis[MAXN];

    bool vis[MAXN];

    int num[MAXN];

    int que[MAXN*MAXN];

bool spfa(double mid)

{

    double val;

    for(int i=0;i<=n;i++)

    {

        dis[i]=inf;

        vis[i]=false;

        num[i]=0;

    }

    dis[1]=0;

    int headt,tail;

    headt=0;tail=0;

    que[tail++]=1;

    vis[1]=true;

    num[1]++;

    while(headt!=tail)

    {

        int v=que[headt];

        headt++;

        vis[v]=false;

        for(int i=head[v];i!=-1;i=edge[i].next)

        {

            int u=edge[i].u;

            val=mid*edge[i].len-a[u];

            if(dis[v]+val<dis[u])

            {

                dis[u]=dis[v]+val;

                if(!vis[u])

                {

                    que[tail++]=u;

                    vis[u]=true;

                    num[u]++;

                    if(num[u]>=n)

                    {

                        return false;

                    }

                }

            }

        }

    }

    return true;

}

int main()

{

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        temp=0;

    for(int i=1;i<=n;i++)

    {

        scanf("%d",&a[i]);

    }

    memset(head,-1,sizeof(head));

    for(int i=1;i<=m;i++)

    {

        int v,w,c;

        scanf("%d%d%d",&v,&w,&c);

        addEdge(v,w,c);

    }

    double  mid=0;double ans=0;

    double l=0;double r=2000;

    while(r-l>=0.001)

    {

        mid=(l+r)/2.0;

        if(spfa(mid))

        {

            r=mid; //减小ans；

        }

        else

        {

            ans=mid;

            l=mid;

        }

    }

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

    }

    return 0;

}