【算法】01分数规划-最优比率环

【题意】给定有向图，点有收益，边有代价，重复经过的话收益不叠加而代价叠加，求从任意点开始最后回归该点的(收益/代价)最大。

【题解】

和普通的分数规划不同，这里的方案选择必须是一个环。首先有一个重要的结论：答案一定是一个简单环。

（简单证明：假设当前复杂环为两个简单环有一点重复（该点收益S），令x1/y1>x2/y2，总环是(x1+x2-S)/(y1+y2)，即要证x1/y1>(x1+x2-S)/(y1+y2)，将式子展开并代入第一个式子即可得证）

由于是一个简单环，每条边就放一个端点的收益即可。二分答案，将-d[i]赋值到每条边上，然后spfa判负环。

 

然后是spfa判断负环。

使用DFS的spfa：可以在发现更新到之前更新过的节点就认为是负环（从x跑出去最后又回来更新x，说明跑的这段路是负数）。

spfa的d数组(最短路)全部初始化为0(即只更新路径为负的)，相当于设置一个起点向所有点连容量为0的边，因为是全图找负环。

只要能访问到负环上的一个点，就一定能找出整个负环。

确认某个曾访问的节点是祖先，这是DFS的特性和优势。

已经更新过的d不改回，这样可以保证最坏复杂度就是全图进行一次spfa。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=1010,maxM=5010;struct edge{
    int v,from;double w;}e[maxM];int first[maxn],tot,a[maxn],b[maxM],n,m;double d[maxn];bool vis[maxn],ok;int read(){    char c;int s=0,t=1;    while(!isdigit(c=getchar()))if(c=='-')t=-1;    do{s=s*10+c-'0';}while(isdigit(c=getchar()));    return s*t;}void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}void spfa(int x){    if(ok)return;    vis[x]=1;    for(int i=first[x];i;i=e[i].from)if(d[e[i].v]>d[x]+e[i].w){        if(vis[e[i].v]){ok=1;break;}        d[e[i].v]=d[x]+e[i].w;        spfa(e[i].v);    }    vis[x]=0;}bool check(double L){    for(int i=1;i<=tot;i++)e[i].w=L*b[i]-a[e[i].v];    memset(d,0,sizeof(d));    //memset(vis,0,sizeof(vis));//    ok=0;    for(int i=1;i<=n;i++){        spfa(i);        if(ok)return 1;    }    return 0;}int main(){    n=read();m=read();    for(int i=1;i<=n;i++)a[i]=read();    int u,v,w;    for(int i=1;i<=m;i++){        u=read();v=read();w=read();        insert(u,v);        b[i]=w;    }    double l=0,r=10100,mid;//    while(r-l>1e-3){        mid=(l+r)/2;        if(check(mid))l=mid;        else r=mid;    }    printf("%.2lf",l);    return 0;}