BZOJ1486 HNOI2009 最小圈

---

Description

---

应该算是01分数规划的裸板题了吧。。但是第一次写还是遇到了一些困难，vis数组不清零之类的
假设一个答案成立，那么一定可以找到一个环使得其边权和大于等于边数∗ans。
可以发现答案是具有二分性的，二分出一个临时答案ans′，并且用ans′对每条边进行约束，再用深搜SPFA判断一下负环，如果有负环说明当前解可行，继续二分就好了。
注意题目要求保留到小数点后八位，多开一点二分次数防止精度不够啊

---

/**************************************************************

    Problem: 1486

    User: yangkai

    Language: C++

    Result: Accepted

    Time:2292 ms

    Memory:1648 kb

****************************************************************/

#include<bits/stdc++.h>

using namespace std;

int read(){

    int ans=0,w=1;char c=getchar();

    while(c!='-'&&!isdigit(c))c=getchar();

    if(c=='-')w=-1,c=getchar();

    while(isdigit(c))ans=ans*10+c-'0',c=getchar();

    return ans*w;

}

#define N 3010

#define M 10010

#define INFF 10000000

int n,m,tot,head[N];

struct Edge{int v,next;double w;}E[M];

void add(int u,int v,double w){

    E[++tot]=(Edge){v,head[u],w};head[u]=tot;

}

int u[M],v[M],vis[N];

double w[M],dis[N];

void build(double val){

    for(int i=1;i<=n;i++)head[i]=0;tot=0;

    for(int i=1;i<=m;i++)add(u[i],v[i],w[i]-val);

}

bool flag=0;

void SPFA(int x){

    vis[x]=1;

    for(int i=head[x];i;i=E[i].next){

        int y=E[i].v;

        if(dis[x]+E[i].w<dis[y]){

            if(vis[y]){flag=1;break;}

            else{

                dis[y]=dis[x]+E[i].w;

                SPFA(y);

            }

        }

    }

    vis[x]=0;

}

int main(){

    n=read();m=read();

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

        u[i]=read(),v[i]=read();

        scanf("%lf",&w[i]);

    }

    double l=-INFF,r=INFF;

    for(int p=1;p<=60;p++){

        double mid=(l+r)/2;

        build(mid);

        flag=0;

        for(int i=1;i<=n;i++){

            memset(vis,0,sizeof(vis));

            memset(dis,0,sizeof(dis));

            SPFA(i);

            if(flag)break;

        }

        if(flag)r=mid;

        else l=mid;

    }

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

    return 0;

}