在图中找一个环，使得环上边权之和除以节点个数最小，求这个最小平均值

[HNOI 2009] 最小圈

题解

分数规划思想
二分平均值，然后对于每条边，我们都减去这个值
接着我们在图中找负环，如果负环存在，则说明答案过大，否则答案过小

代码

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxd = 1e4+10;
const int maxn = 3e3+10;
struct{
    int v,net;
    double w;
}e[maxd];
int f[maxn],eid,n,m;
bool vis[maxn];
double dist[maxn];
void insert(int a,int b,double c)
{
    e[eid].v = b;
    e[eid].w = c;
    e[eid].net = f[a];
    f[a] = eid++;
}
void init()
{
    memset(f,-1,sizeof(f));
    eid = 0;
}
bool dfs(int x,double mid)
{
    vis[x] = 1;
    for(int i=f[x];i+1;i=e[i].net)
    {
        int to = e[i].v;
        if(dist[to] > dist[x] + e[i].w - mid)
        {
            dist[to] = dist[x] + e[i].w - mid;
            if(vis[to] || dfs(to,mid))
            {
                vis[x] = 0;
                return true;
            }
        }
    }
    vis[x] = 0; return false;
}
bool check(double mid)
{
    memset(dist,0,sizeof(dist));
    for(int i=1;i<=n;i++)
        if(dfs(i,mid)) return true;
    
    return false;
}
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("k.out","w",stdout);
    int a,b,c;init();
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        insert(a,b,(double)c);
    }
    double l = -1e7, r = 1e7,ans;
    while(l<=r)
    {
        double mid = (l+r)/2;
        if(check(mid))
        {
            ans = mid;
            r = mid-0.000000001;
        }
        else l = mid + 0.000000001;
    }
    printf("%.8lf",ans);
    return 0;
}