洛谷2868 [USACO07DEC]Sightseeing Cows

题意

给出一个有向图，有边权 $w_i$ 和点权 $s_i$ 。要求找一个环，使 $\dfrac{\sum s_i}{\sum w_i}$ 最大。

其中点数 $N\le 1000$ ，边数 $M\le 5000$ 。

题解

$0/1$ 分数规划。设当前二分值为 $mid$ ，题目即为

$$\dfrac{\sum s_i}{\sum w_i} > mid$$

$$\sum (s_i-mid\times w_i) > 0$$

$$\sum (mid\times w_i-s_i) < 0$$

把边权看成 $mid\times w_i-s_i$ 判负环就行了。

#include<bits/stdc++.h>
#define eps 1e-4

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    int next,to,w;
} edge[5005];
bool vis[1005];
double dis[1005];
int cnt,head[1005],n,m,a,b,c,s[1005];

inline void add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

bool spfa(int x,double mid)
{
    if (vis[x]) return 0;
    vis[x]=1;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to,w=edge[i].w;
        if (dis[x]+mid*w-1.0*s[y]<dis[y])
        {
            dis[y]=dis[x]+mid*w-1.0*s[y];
            if (vis[y] || spfa(y,mid)) return vis[x]=0,1;
        }
    }
    return vis[x]=0,0;
}

inline bool check(double mid)
{
    memset(dis,0,sizeof(dis));
    for (int i=1;i<=n;i++)
    {
        if (!spfa(i,mid)) continue;
        return 1;
    }
    return 0;
}

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++) s[i]=read();
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read(); c=read();
        add(a,b,c);
    }
    double l=0,r=1000000;
    while (r-l>eps)
    {
        double mid=(l+r)/2;
        if (check(mid)) l=mid;
        else r=mid;
    }
    return !printf("%.2f",l);
}