[HNOI2009]最小圈

二分 负环

题面

给一有向图，询问圈的最小平均值。

解析

先二分圈的平均值的最小值，记当前答案为$mid$。
这时候，把所有的边权都减掉$mid$ 。
这样判断原图中是否包含有平均值小于等于$mid$的圈，就转化成了判断新图中是否包含有负环。用$SPFA$判断负环即可。
Update:但我这个程序过不了第二个样例。。。

// luogu-judger-enable-o2
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#define ll long long
#define re register
#define il inline
#define eps 1e-10
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=5000;
int n,m,h[N],cnt;double mid,dis[N];
bool vis[N],viss;
struct Edge{int to,next,w;}e[N<<1];
il void add(re int u,re int v,re int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void wri(re int x)
{
  if(x<0) putchar('-'),x=-x;
  if(x>9) wri(x/10);
  putchar(x%10+'0');
}
il void SPFA(re int u)
{
  if(viss) return;
  vis[u]=1;
  for(re int i=h[u];i;i=e[i].next)
    {
      re int v=e[i].to;
      if(dis[v]>dis[u]+e[i].w-mid)
    {
      dis[v]=dis[u]+e[i].w-mid;
      if(vis[v]) {viss=1;return;}
      SPFA(v);
    }
    }
  vis[u]=0;
}
il int check()
{
  memset(dis,0,sizeof(dis));memset(vis,0,sizeof(vis));viss=0;
  fp(i,1,n)
    {
      SPFA(i);
      if(viss) return 1;
    }
  return 0;
}
int main()
{
   n=gi();m=gi();
   fp(i,1,m)
    {
       re int u=gi(),v=gi(),w=gi();
       add(u,v,w);
    }
   re double l=-1e33,r=1e33;
   while(l+eps<r)
     {
       mid=(l+r)/2;
       if(check()) r=mid;else l=mid;
    }
   printf("%.8lf\n",l);
  return 0;
}