题目描述
给出一张图，求图上的一个环使这条环的平均长度最小。
思路
这道题其实和Word Rings相同，只是已经给出图了，直接在图上跑dfs即可。
代码
#include <bits/stdc++.h> using namespace std; const int N=3300,M=1e4+10; const double eps=1e-10; int nxt[M],to[M],tot,head[N]; int vis[N],n,f; double dis[N],w[M]; void add_edge(int x,int y,double v) { nxt[++tot]=head[x]; head[x]=tot; to[tot]=y; w[tot]=v; } void spfa(int u,int st,double aver) { if(f)return ; vis[u]=st; for(int i=head[u];~i;i=nxt[i]) { int v=to[i]; // cout<<v<<' '<<i<<endl; if(dis[u]+w[i]-aver<dis[v]) { dis[v]=dis[u]+w[i]-aver; if(!vis[v])spfa(v,st,aver); if(vis[v]==st){f=1;return ;} } } vis[u]=0; } bool check(double aver) { memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); f=0; for(int i=1;i<=n;i++) { spfa(i,i,aver); if(f)break ; } return f; } int main() { memset(head,-1,sizeof(head)); int m; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y;double z; scanf("%d%d%lf",&x,&y,&z); add_edge(x,y,z); } // for(int i=1;i<=tot;i++) // printf("%lf\n",w[i]); double l=-10000000,r=10000000,ans; while(r-l>eps) { // cout<<l<<' '<<r<<endl; double mid=(r+l)/2; if(check(mid))ans=mid,r=mid; else l=mid; } printf("%.8lf",ans); return 0; }