本文共 1632 字，大约阅读时间需要 5 分钟。
二分答案 ans ，将所有边都减去 ans ，判断负环。
#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define lck_max(a,b) ((a)>(b)?(a):(b))const int maxn=505;const double eps=1e-3,INF=1e9;inline int read(){ int xs=0,kr=1;char ls; ls=getchar(); while(!isdigit(ls)) { if(!(ls^45)) kr=-1; ls=getchar(); } while(isdigit(ls)) { xs=(xs<<1)+(xs<<3)+(ls^48); ls=getchar(); } return kr*xs;}int n,m,u,v;double w;struct hh{ int nex,to; double w;}t[maxn];int head[maxn],cnt;inline void add(int nex,int to,int w){ t[++cnt].nex=head[nex]; t[cnt].to=to; t[cnt].w=w; head[nex]=cnt;}double d[maxn];int num[maxn];bool inq[maxn];queue q;inline bool spfa(double mid){ for(int i=1;i<=n;i++) d[i]=INF; memset(inq,0,sizeof(inq)); memset(num,0,sizeof(num)); for(int i=1;i<=n;i++) d[i]=0.0,inq[i]=true,q.push(i); while(!q.empty()) { int u=q.front();q.pop();inq[u]=false; for(int i=head[u];i;i=t[i].nex) { int v=t[i].to;double w=t[i].w-mid; if(d[v]>d[u]+w) { d[v]=d[u]+w; if(!inq[v]) { inq[v]=true,q.push(v); if(++num[v]>n) return true; } } } } return false;}int T,cas;int main(){ T=read(); while(T--) { cas++; printf("Case #%d: ",cas); n=read();m=read(); memset(head,0,sizeof(head)); double l=0,r=0; for(int i=1;i<=m;i++) u=read(),v=read(),w=read(),add(u,v,w),r=lck_max(r,w); if(!spfa(r+1)) puts("No cycle found."); else { while(r-l>eps) { double mid=(l+r)/2; if(spfa(mid)) r=mid; else l=mid; } printf("%.2f\n",l); } }return 0;}
转载于:https://www.cnblogs.com/lck-lck/p/9837626.html