26

// Algorithm: Karp’s minimum mean (or average) weight cycle algorithm
//            Strongly Connected Component

struct NODE {
    int v, w;
    NODE() {}
    NODE(int _, int __) {
        v = _;
        w = __;
    }
};
struct NODE2{
    int node, fTime;
    friend bool operator<(NODE2 A, NODE2 B) {
        return A.fTime > B.fTime;
    }
};
vector <NODE> G[MAXN], G_REV[MAXN], graph[MAXN];
bool vis[MAXN];
int timer;
int dis[MAXN];
int finish[MAXN];
void dfs(int u) {
    dis[u] = timer++;
    for (NODE e : G[u]) {
        if (vis[e.v])
            continue;
        vis[e.v] = 1;
        dfs(e.v);
    }
    finish[u] = timer++;
}
set <int> SCC;
void dfs2(int u) {
    SCC.insert(u);
    for (NODE e : G_REV[u]) {
        if (vis[e.v])
            continue;
        vis[e.v] = 1;
        dfs2(e.v);
    }
}
int dp[MAXN][MAXN];
double KARPS() {
    int tNode = SCC.size();
    int u;
    for (auto it : SCC) {
        u = it;
        break;
    }
    int here[MAXN] = {0};
    for (int n : SCC) {
        here[n] = 1;
    }
    for (int n : SCC) {
        for (NODE e : G[n]) {
            if (!here[e.v])
                continue;
            graph[n].push_back(e);
        }
    }
    for (int i = 0; i < MAXN; i++) {
        for (int j = 0; j < MAXN; j++) {
            dp[i][j] = INF;
        }
    }
    dp[0][u] = 0;

    for (int k = 1; k <= tNode; k++) {      // edge
        for (int u : SCC) {                 // node num
            for (NODE e : graph[u]) {       // child
                if (dp[k - 1][u] != INF) {
                    int wt = dp[k - 1][u] + e.w;
                    dp[k][e.v] = min(dp[k][e.v], wt);
                }
            }
        }
    }
    double mean[MAXN];
    for (int i = 0; i < MAXN; i++) {
        mean[i] = -1;
    }
    for (int u : SCC) {
        int fCost = dp[tNode][u];
        if (fCost == INF)
            continue;
        for (int k = 0; k < tNode; k++) {
            int nowCost = dp[k][u];
            if (nowCost != INF && nowCost <= fCost) {
                double m = ((double)fCost - nowCost) / (tNode - k);
                mean[u] = max(mean[u], m);
            }
        }
    }
    double res = INF;
    for (int u : SCC) {
        if (mean[u] == -1) continue;
        res = min(res, mean[u]);
    }
    return res;
}