对于一张有向图，要你求图中最小圈的平均值最小是多少，即若一个圈经过k个节点，那么一个圈的平均值为圈上k条边权的和除以k，现要求其中的最小值。
输入格式：
第一行2个正整数，分别为n和m
以下m行，每行3个数，表示边连接的信息，
输出格式：
一行一个数，表示最小圈的值，保留8位小数。
若设边权为v，那么50000n≤3000,m≤10000,v≤50000。
此题要求最小圈平均值最小是多少。如果这个圈的平均值是负数那么这就是一个负环。判断负环可以用spfa，然后用二分答案做就行了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef double db; const int maxn=3005; const int maxm=10005; const db eps=1e-10; inline void read(int &x){ x=0; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} } int n,m,tot; int head[maxn]; double dis[maxn]; bool vis[maxn]; struct node{ int next,to,dist; }e[maxm<<1]; inline void ins(int from,int to,int dist){ e[++tot].next=head[from]; e[tot].to=to; e[tot].dist=dist; head[from]=tot; } bool spfa(int x,db lim){ vis[x]=true; for(int i=head[x];i;i=e[i].next){ int to=e[i].to; if(dis[to]>dis[x]+(db)e[i].dist-lim){ if(vis[to]) return true; else{ dis[to]=dis[x]+(db)e[i].dist-lim; if(spfa(to,lim)) return true; } } } return vis[x]=false; } inline bool pd(double lim){ memset(vis,0,sizeof(vis)); memset(dis,0,sizeof(dis)); for(int i=1;i<=n;++i) if(spfa(i,lim)) return true; return false; } int main(){ read(n);read(m); for(int i=1;i<=m;++i){ int u,v,w; read(u);read(v);read(w); ins(u,v,w); } db l=0.0,r=50000.0,mid; while(r-l>eps){ mid=(l+r)/2.0; if(pd(mid)) r=mid; else l=mid; } printf("%.8lf",r); return 0; }
原文：http://www.cnblogs.com/huihao/p/7757977.html