洛谷3199（01分数规划、判负环）

最小平均值的环。二分答案以后根据式子将问题转化为：每条边减去mid后是否存在负环，若全是正环说明ans给小了，存在负环则说明存在一个更小的ans。
get到一个新的判负环手法。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define pb push_back
#define fi first
#define se second
using namespace std;

typedef double db;
const int maxn = 3e3 + 5;
const db eps = 1e-9;

int n, m;
vector<pair<int, db>> adj[maxn];
db l, r, mid;
db dis[maxn];
bool vis[maxn];

bool dfs(int cur) {//注意此题为有向图
    vis[cur] = 1;
    for (auto i : adj[cur])
        if (dis[i.fi] > dis[cur] + i.se - mid) {
            dis[i.fi] = dis[cur] + i.se - mid;
            if (vis[i.fi] || dfs(i.fi))
                return vis[cur] = 0, 1;
        }
    return vis[cur] = 0;
}

bool check() {
    memset(dis, 0, sizeof dis);
    for (int i = 1; i <= n; i++)
        if (dfs(i)) 
            return 1;
    return 0;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v; db cost;
        scanf("%d %d %lf", &u, &v, &cost);
        adj[u].pb({v, cost});

        if (cost >= 0)  r += cost;
        else    l += cost;
    }
    while (r - l > eps) {
        mid = (l + r) / 2.0;
        if (check())    r = mid;
        else    l = mid;
    }
    return !printf("%.8lf\n", l);
}

洛谷3199（01分数规划、判负环）

原文：https://www.cnblogs.com/AlphaWA/p/10799611.html