画一个 n 个节点，m 条边的带权有向图，想从中找出权值的平均值最小的环。有向图中可能不存在环，求最小的平均权值。

共 m+1 行。

第$1行，2个整数n和m，表示点数和边数。

第$2 ~ m+1行，每行3个正整数 $u，v，w，表示u与v之间有一条权值为w的有向边。

如果输入数据无环，输出“PaPaFish is laying egg!”。（不含引号）

否则输出一个浮点数 ans，表示所有环中，权值的平均值最小的环的平均权值。答案保留2位小数。

【数据规模】

对于前40%的数据 n≤50，m≤5000；

对于100%的数据 $≤n≤1000，1≤m≤10000，0≤w≤10000000

二分答案，dfs判环

```

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
const int N = 1e5 + 10;
int n, m;
int h[N],ne[N],e[N];
double w[N];
double dis[N];
int idx;
bool st[N];
void add(int a,int b,double c)
{
    e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++;
}
bool bj;
double mid;
bool spfa(int t)
{
    st[t] = 1;
    for(int i = h[t]; ~i ; i = ne[i])
    {
        int j = e[i];
        if(dis[j] <= dis[t] + w[i] - mid) continue;
        if(st[j] && dis[t] + w[i] - mid <= 0) return 1;
        dis[j] = dis[t] + w[i] - mid;
        if(!st[j] && spfa(j)) return 1;
    }
    st[t] = 0;
    return 0;
}

bool check(double k)
{
    memset(st,0,sizeof(st));
    memset(dis,0,sizeof(dis));
    for(int i = 1;i <= n; i++)
    {
        if(!dis[i] && spfa(i)) return 1;
    }
    return 0;
}

int main()
{
    scanf("%d %d",&n,&m);
    memset(h, -1,sizeof(h));
    double L = 0, R = 10000000 + 120;
    double ans = -1;
    double eps  = 1e-3;
    for(int i = 1; i <= m; i++)
    {
        int a, b;
        double c;
        scanf("%d %d %lf",&a,&b,&c);
        add(a, b, c);
    }
    while(R - L >= 0.0004)
    {
         mid = (R + L) / 2;
        if(check(mid))
        {
            R = mid;
            ans = mid;
        }
        else L = mid;
    }
    if(ans != -1)
    printf("%.2lf",ans);
    else puts("PaPaFish is laying egg!");
    return 0;
}

```