洛谷3199 [HNOI2009]最小圈

题意

定义圈的平均值为一个环上所有边的权值和 $\div$ 边的个数。给出一个有向图，求最小圈的平均值，保留 $8$ 位小数。

其中点数 $n\le 3000$ ，边数 $m\le 10000$ 。

题解

$0/1$ 分数规划，直接二分答案 $mid$ ，然后对每条边减去 $mid$ 再跑 $spfa$ 判负环。如果有负环就缩小上界，否则增大下界。

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

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[10005];
int cnt,head[3005],n,m,a,b,c;
double dis[3005];
bool vis[3005];

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;
}

inline 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*1.0;
        if (dis[x]+w-mid<dis[y])
        {
            dis[y]=dis[x]+w-mid;
            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;
}

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