https://vjudge.net/problem/UVA-11090
平均权值最小的回路
为后面的做个铺垫
二分最小值，每条边权减去他，有负环说明有的回路平均权值小于他
spfa求负环的时候可以先把所有点加到队列里,d[i]=0
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N=55; const double eps=1e-3,INF=1e9; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,m,u,v;double w; struct edge{ int v,ne; double w; }e[N*N]; int h[N],cnt=0; inline void ins(int u,int v,int w){ cnt++; e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt; } double d[N]; int q[N],head,tail,inq[N],num[N]; inline void lop(int &x){if(x==N) x=1;} bool spfanc(double mid){ for(int i=1;i<=n;i++) d[i]=INF; head=tail=0; memset(inq,0,sizeof(inq)); memset(num,0,sizeof(num)); for(int i=1;i<=n;i++) d[i]=0.0,inq[i]=1,q[tail++]=i; while(head!=tail){ int u=q[head++];inq[u]=0;lop(head); for(int i=h[u];i;i=e[i].ne){ int v=e[i].v;double w=e[i].w-mid; if(d[v]>d[u]+w){ d[v]=d[u]+w; if(!inq[v]){ inq[v]=1,q[tail++]=v,lop(tail); if(++num[v]>n) return true; } } } } return false; } int main(){ int T=read(),cas=0; while(T--){ printf("Case #%d: ",++cas); n=read();m=read(); cnt=0;memset(h,0,sizeof(h)); double l=0,r=0; for(int i=1;i<=m;i++) u=read(),v=read(),w=read(),ins(u,v,w),r=max(r,w); if(!spfanc(r+1)) puts("No cycle found."); else{ while(r-l>eps){ double mid=(l+r)/2; if(spfanc(mid)) r=mid; else l=mid; } printf("%.2f ",l); } } }