bzoj 1486: [HNOI2009]最小圈

.

题意：找出有向图中平均值最小的环。
题解：01分数规划。

#include<bits/stdc++.h>
using namespace std;

int n,m,num=0,fst[3010],x[10010],y[10010];
double c[10010],eps=1e-10,dis[3010];
struct edge
{
    int x,y,n;
    double c;
}e[10010];
bool v[3010],tf;

void ins(int x,int y,double c)
{
    e[++num]={x,y,fst[x],c};
    fst[x]=num;
}
void dfs(int x)
{
    if(v[x])
    {
        tf=1;
        return;
    }
    v[x]=1;
    for(int i=fst[x];i;i=e[i].n)
    {
        int y=e[i].y;
        if(dis[y]>dis[x]+e[i].c)
        {
            dis[y]=dis[x]+e[i].c;
            dfs(y);
            if(tf)
            break;
        }
    }
    v[x]=0;
}
void build(double hh)
{
    num=0;
    memset(fst,0,sizeof(fst));
    for(int i=0;i<m;i++)
    ins(x[i],y[i],c[i]-hh);
}
bool chk(double x)
{
    build(x);
    memset(v,0,sizeof(v));
    memset(dis,0,sizeof(dis));
    tf=0;
    for(int i=1;i<=n;i++)
    {
        dfs(i);
        if(tf)
        return 1;
    }
    return 0;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%lf",&x[i],&y[i],&c[i]);
    }
    double l=-1e7,r=1e7;
    while(l+eps<r)
    {
        double md=(l+r)/2;
        if(chk(md))
        r=md;
        else
        l=md;
    }
    printf("%.8lf",l);
}