Article From:https://www.cnblogs.com/zhoushuyu/p/9060853.html

bzoj
luogu

# meaning”

You have a directed graph that guarantees connectivity and guarantees that there is at least one ring.
You need to find a ring that minimizes the average weight of the ring.
The average value of a ring is defined as the total weight of a ring divided by the ring length.

# sol

Fractional planning. It can be seen as every side\(b_i=1\)
Two points one\(mid\)，order\(d_i=w_i-mid\)，Then determine whether there is a negative loop in the graph.
The simplest of negative rings\(O(n^2)\)The algorithm can be used.

# code

``````#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 10005;
struct edge{int to,nxt;double w;}a[N];
double dis[N];
}
bool cir(int u,double k){
vis[u]=1;
if (dis[a[e].to]>dis[u]+a[e].w-k){
dis[a[e].to]=dis[u]+a[e].w-k;
if (vis[a[e].to]||cir(a[e].to,k)) return true;
}
vis[u]=0;return false;
}
bool check(double k){
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
for (int i=1;i<=n;++i) if (cir(i,k)) return true;
return false;
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=m;++i){
int u,v;double w;
scanf("%d %d %lf",&u,&v,&w);
}
double l=-2e7,r=2e7;
while (r-l>1e-9){
double mid=(l+r)/2;
if (check(mid)) r=mid;
else l=mid;
}
printf("%.8lf\n",l);
return 0;
}``````