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

这题主要是分析出如何确定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
    
     #include
     
      #include
      
       #define MAXN 1052#define inf 10000000using 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
       
        =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;}