题意

给你一个有向图，问你定义一个环的平均值为这个环上所有边的平均值，问你最小的环的平均值是多少。

做法

1.   二分答案。

2.   如果平均数为mid；则若这个环的每条边长度是x1~xn，就有（x1-mid）+（x2-mid）+……+（xn-mid）=0；

      所以只要把所有边都减去mid，然后判断图是否存在负环……

代码

#include
     
      #include
      
       #include
       
        #include
        
         #define INF 50000000000.0#define MN 50#define eps 1e-5using namespace std;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9') {
   if(ch=='-') f=-1;ch=getchar();}    while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';ch=getchar();}    return x*f;}struct data{
   int t;double w;};vector
          pic[MN+5];void ins(int u,int v,double c){data e;e.t=v;e.w=c;pic[u].push_back(e);}int n,m,a,b;double c,dis[MN+5];bool mark[MN+5];int cnt[MN+5],q[MN*MN+5],top,tail;void huanyuan(double f){    for(int i=1;i<=n;i++)    for(int j=0;j
          
           =tail){ int u=q[tail++]; mark[u]=0; for(int i=0;i
           
            n){huanyuan(f);return 1;} mark[pic[u][i].t]=1; q[++top]=pic[u][i].t; } } } huanyuan(f); return 0;}int main(){ int Case=read(); for(int cas=1;cas<=Case;cas++){ n=read(); m=read(); for(int i=1;i<=n;i++) pic[i].clear(); double Max=0.0; for(int i=1;i<=m;i++) a=read(),b=read(),scanf("%lf",&c),ins(a,b,c); printf("Case #%d: ",cas); double lef=0.0,rig=10000005; while(rig-lef>1e-4){ double mid=lef+(rig-lef)/2; if(spfa(mid)) rig=mid; else lef=mid; } if(lef<=10000001)printf("%.2lf\n",lef); else printf("No cycle found.\n"); } return 0;}
           
          
        
       
      
     

 ————————————————————————————————————————————————————

来自Paper Cloud的博客，未经允许请勿转载，谢谢。