https://zybuluo.com/ysner/note/1144886
题面
给一有向图，询问圈的最小平均值。
解析
先二分圈的平均值的最小值，记当前答案为(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
",l);
return 0;
}