题意及题解参见lrj训练指南
#include<bits/stdc++.h> using namespace std; const double INF=1e18; const int maxn=55; const int maxm=5005; int n,m; struct Edge { int to,next; double d; Edge(){} Edge(int to_,int next_,double d_) { to=to_,next=next_,d=d_; } }; Edge edge[maxm]; int head[maxn],tot; bool inq[maxn]; double d[maxn]; int p[maxn]; int cnt[maxn]; void init() { memset(head,-1,sizeof(head)); tot=0; } void addedge(int u,int v,double d) { edge[tot]=Edge(v,head[u],d); head[u]=tot++; } // 顶点编号0~n-1共n个点 // 返回值表示 从s出发，能否遇到负环 bool spfa(int s,int n) { queue<int> Q; for(int i=0;i<n;i++) d[i]=INF; memset(inq,false,sizeof(inq)); memset(cnt,0,sizeof(cnt)); Q.push(s),inq[s]=true,d[s]=0; while(!Q.empty()) { int u=Q.front();Q.pop(); inq[u]=false; for(int i=head[u];~i;i=edge[i].next) { Edge& e=edge[i]; if(d[e.to]>d[u]+e.d) { d[e.to]=d[u]+e.d; p[e.to]=i; if(!inq[e.to]) { Q.push(e.to),inq[e.to]=true; if(++cnt[e.to]>=n) return true;//存在负环 } } } } return false; //无负环 } bool ok(double x) { for(int i=0;i<tot;i++) edge[i].d-=x; bool ret=spfa(0,n+1); for(int i=0;i<tot;i++) edge[i].d+=x; return ret; } int main() { int T,kase=0; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); init(); double ud=0; while(m--) { int u,v; double d; scanf("%d%d%lf",&u,&v,&d); addedge(u,v,d); ud=max(ud,d); } for(int i=1;i<=n;i++) addedge(0,i,ud+1); printf("Case #%d: ",++kase); if(!ok(ud+1)) { puts("No cycle found."); continue; } double l=0,r=ud; while(r-l>1e-3) { double mid=(l+r)/2; if(ok(mid)) r=mid; else l=mid; } printf("%.2lf ",l); } }