bzoj1690:[Usaco2007 Dec]奶牛的旅行（分数规划+spfa判负环）

　　PS:此题数组名皆引用：戳我

题目大意：有n个点m条有向边的图，边上有花费，点上有收益，点可以多次经过，但是收益不叠加，边也可以多次经过，但是费用叠加。求一个环使得收益和/花费和最大，输出这个比值。

显然这就是经典的分数规划题啊，就是最优比率环，那么就二分答案，将所有边（u，v）的边权改为【v的点权-（u，v）原边权*mid】（因为d[i]=a[i]-L*b[i]），然后判一下是否有正环，有的话就说明有更优的答案（F(L)=sigma(a[i]*x[i])-L*sigma(b[i]*x[i])>0即sigma(a[i]*x[i])/sigma(b[i]*x[i])>L），缩小范围继续二分。判正环有够别扭的，那就全部改成相反数然后判负环吧233333

代码如下：

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<queue>

using namespace std;

struct zs{int too,pre;double dis;}e[];

struct poi{int pos;double dis;};

priority_queue<poi>q;

bool operator <(poi a,poi b){return a.dis-b.dis>1e-;}

int n,m,x,y,now,tot,num[],last[];

bool v[];

double l,r,mid,dis[],fun[];

bool spfa(int x)

{

    for(int i=;i<=n;i++)dis[i]=;v[x]=true;q.push((poi){,});dis[]=;

    while(!q.empty())

    {

        int i,too;

        for(i=last[now=q.top().pos],too=e[i].too,q.pop();i;i=e[i].pre,too=e[i].too)

        {

            double dist=e[i].dis*mid-fun[too];

            if(dis[too]-dis[now]-dist>1e-)

            {

                dis[too]=dis[now]+dist;

                if(!v[too])v[too]=,q.push((poi){too,e[i].dis}),num[too]++;

                if(num[too]>)return ;

            }

        }

        v[now]=;

    }

    return ;

}

int main()

{

    scanf("%d %d",&n,&m);

    for(int i=;i<=n;i++)scanf("%lf",&fun[i]);

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

    {

        scanf("%d %d %lf",&x,&y,&e[++tot].dis);

        e[tot].too=y;e[tot].pre=last[x];last[x]=tot;

    }

    l=;r=;

    while(r-l>1e-)

    {

        memset(v,,sizeof(v));

        memset(num,,sizeof(num));

        mid=(l+r)/;

        if(spfa())l=mid;

        else r=mid;

    }

    printf("%.2lf",l);

}

巴特西

bzoj1690:[Usaco2007 Dec]奶牛的旅行（分数规划+spfa判负环）

最新文章

热门文章