给出一张图，点数为L，边数P，并给出边的边权\(\{b_i\}\),再给处每个点的点权，求一条起点和终点相同的路径，并使其点权之和除以边权之和最大，注意，路径中点权只能被计算一次，而边权可以重复计算， (2 ≤ L ≤ 1000)， (2 ≤ P ≤ 5000)。

解

显然为分数规划问题，关键在点权与边权不对应上，于是自然的想法是点权移边权，而一条起点与终点相同的路径即一个联通分量，所以问题现在在于点权移边权后只对环成立，而不对联通分量成立，于是考虑证明联通分量对结果没有影响，于是设一个大环它的路径长\(b_1\)，点权\(a_1\),一个小环路径长\(b_2\),点权\(a_2\),设他们是套在一起的环，所以会有重叠的地方。

不难得知,大环的比率为\(\frac{a_1}{b_1}\)，小环比率\(\frac{a_2}{b_2}\)，而套在一起的环比率仍按照不去点权算为\(\frac{a_1+a_2}{b_1+b_2}\),由分数三角不等式结论，我们知道\(\frac{a_1+a_2}{b_1+b_2}\leq max(\frac{a_1}{b_1},\frac{a_2}{b_2})\)

所以我们可以知道实际上环套环，即联通分量对结果没有影响，于是移点下边，接下来照着最优比率环的基本套路即可，但是注意此处要算出一个具体的比较大的ans很难做到，于是迭代就不能使用了，但是你的聪明才智或许能想到一种好的解决办法。

参考代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define il inline#define ri register#define exact 0.000001using namespace std;struct point{    int next,to,a,b;    double c;}ar[5001];int at;bool is[1001];double dis[10001];int f[1001],head[1001],n,    t1[4000001],tot[1001];il bool check(double);il double dfs(double,double);il void link(int,int,int,int),read(int&);int main(){    int m,i,j,k;    read(n),read(m);    for(i=1;i<=n;++i)read(f[i]);    while(m--)read(i),read(j),read(k),                  link(i,j,f[j],k);    printf("%.2lf",dfs(0,100));    return 0;}il bool check(double x){    int i,h(0),t(0);    memset(is,0,sizeof(is)),memset(tot,0,sizeof(tot)),        memset(dis,0,sizeof(dis));    for(i=1;i<=n;++i)t1[++t]=i;    for(i=1;i<=at;++i)        ar[i].c=ar[i].b*x-ar[i].a;    while(h
        
         =n)return true;                }            }    }return false;}il double dfs(double l,double r){    double mid;    while(r-l>exact){        mid=(l+r)/2;        if(check(mid))l=mid+exact;        else r=mid-exact;    }return (l+r)/2;}il void read(int &x){    x&=0;ri char c;while(c=getchar(),c<'0'||c>'9');    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();}il void link(int x,int y,int a,int b){    ar[++at].a=a,ar[at].b=b,ar[at].to=y;    ar[at].next=head[x],head[x]=at;}