题目地址：洛谷：【P3199】[HNOI2009]最小圈 – 洛谷、BZOJ：Problem 1486. — [HNOI2009]最小圈

题目描述

换句话说就是找图中的环使得环上的边权的平均数最小。

输入输出格式

输入格式：
n, m
u, v, w

输出格式：
答案。

输入输出样例

输入样例#1：

4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3

输出样例#1：

3.66666667

输入样例#2：

2 2
1 2 -2.9
2 1 -3.1

输出样例#2：

-3.00000000

说明

n<=3000, m<=10000

题解

我们先考虑直接找环求平均数是不太可行的，因为图上环可以很多，边数的数据范围不允许平方。但是如果我们有一个数，我们可以验证是否存在满足平均数比这个数大/小的环。
具体而言，我们用看上去很快的被称为DFS-SPFA的东西跑一遍，跑的时候dis数组全部初值为0，边权减掉我们固定的那个数，然后判负环即可。存在负环==存在平均数比这个数小的环。那么外面套个二分答案即可。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <vector>
#include <algorithm>

typedef long long LL;

const int MAXN = 3005;
const double EPS = 1e-10;

struct Edge {
    int to;
    double w;
};

std::vector<Edge> gra[MAXN];
int n, m, ut, vt;
double wt, dis[MAXN];
bool vis[MAXN];

inline bool dfs(int u, double x) {
    vis[u] = true;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i].to;
        if(dis[v] > dis[u] + gra[u][i].w - x + EPS) {
            if(vis[v]) return true;
            dis[v] = dis[u] + gra[u][i].w - x;
            if(dfs(v, x)) return true;
        }
    }
    vis[u] = false;
    return false;
}

inline bool check(double x) {
    memset(vis, 0, sizeof(vis));
    memset(dis, 0, sizeof(dis));
    for(int i = 1; i <= n; i++) {
        if(vis[i]) continue;
        // dfs returns true represents that there is a negative circle
        if(dfs(i, x)) return true;
    }
    return false;
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d%d%lf", &ut, &vt, &wt);
        gra[ut].push_back(Edge{vt, wt});
    }
    double l = -1e5, r = 1e5;
    while(r - l > EPS) {
        double mid = (l + r) / 2;
        if(check(mid)) r = mid; else l = mid;
    }
    printf("%.8lf", r);
    return 0;
}