题意
给你一个有向图，问你定义一个环的平均值为这个环上所有边的平均值，问你最小的环的平均值是多少。
做法
1. 二分答案。
2. 如果平均数为mid；则若这个环的每条边长度是x1~xn，就有（x1-mid）+（x2-mid）+……+（xn-mid）=0；
所以只要把所有边都减去mid，然后判断图是否存在负环……
代码
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #define INF 50000000000.0 #define MN 50 #define eps 1e-5 using 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<data> 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<pic[i].size();j++) pic[i][j].w+=f; } bool spfa(double f){ huanyuan(-f); memset(mark,0,sizeof(mark)); memset(cnt,0,sizeof(cnt)); top=0; for(int i=1;i<=n;i++) q[++top]=i,dis[i]=INF; tail=1; dis[1]=0.0; mark[1]=1; cnt[1]++; while(top>=tail){ int u=q[tail++]; mark[u]=0; for(int i=0;i<pic[u].size();i++) if(pic[u][i].w+dis[u]+eps<dis[pic[u][i].t]){ dis[pic[u][i].t]=pic[u][i].w+dis[u]; if(!mark[pic[u][i].t]){ if(++cnt[pic[u][i].t]>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 ",lef); else printf("No cycle found. "); } return 0; }
————————————————————————————————————————————————————
来自Paper Cloud的博客，未经允许请勿转载，谢谢。