[HNOI2009] 最小圈

1. 核心推导：从求比值到判负环

目标

我们需要找到一个圈 $C$ ，使得其平均值 $\mu(C)$ 最小：

\text{Minimize } \mu(C) = \frac{\sum_{e \in C} w_e}{|C|}

其中 $|C|$ 是圈中边的数量。

二分答案

这里是题目的核心: 证明题目具有二分性:.

假设我们猜测最终的最小平均值是 $x$ 。

如果存在一个圈，使得它的平均值 $< x$ ，说明答案比 $x$ 更小，我们应该往左找（ $r = mid$ ）。
如果所有圈的平均值都 $\ge x$ ，说明答案就是 $x$ 或者比 $x$ 更大，我们应该往右找（ $l = mid$ ）。

洪水蔓延思考法: 边的权值

公式变形 (Check 函数的灵魂)

判定条件：是否存在一个圈 $C$ ，满足：

\frac{\sum_{e \in C} w_e}{|C|} < x

两边同乘 $|C|$ (因为边数 $>0$ ，不等号方向不变)：

\sum_{e \in C} w_e < x \cdot |C|

\sum_{e \in C} w_e - \sum_{e \in C} x < 0

合并求和项：

\sum_{e \in C} (w_e - x) < 0

结论

二分一个 $x$ 后，我们将图中每一条边 $e$ 的权值 $w_e$ 减去 $x$ ，得到新边权 $w'_e = w_e - x$ 。

问题就变成了：在新图中，是否存在一个边权和 $< 0$ 的圈（负环）？

注：题目要求的是最小值，严格来说判定的是“是否存在负环”。只要存在负环，就说明存在平均值小于 $x$ 的方案。

2. 算法选择：SPFA 判负环

判断图中是否存在负环，常用的算法是 SPFA (Shortest Path Faster Algorithm)。

SPFA 有两种实现方式：

BFS-SPFA（基于广度优先）：稳定，但判负环较慢（需要入队 $N$ 次才判负）。
DFS-SPFA（基于深度优先）：判负环极快。一旦递归路径上重复遇到当前正在访问的节点，就说明找到了环；如果路径权值和减少了，那就是负环。

对于这道题，推荐使用 DFS-SPFA。

虽然 DFS-SPFA 在求最短路时由指数级复杂度的风险，但在判定负环的存在性上，它通常能在找到负环的那一刻立即退出，效率非常高。

3. 代码实现细节

二分范围： $[-10^7, 10^7]$ 。
精度控制：循环 60 到 100 次即可。
图的连通性：虽然题目说图连通，但 SPFA 判负环最稳妥的做法是把所有点都作为潜在起点扫一遍（或者建立一个超级源点）。在 DFS-SPFA 中，我们遍历 $1 \dots N$ ，如果该点没被访问过，就发起一次 DFS。

4. AC 代码

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-07 15:52:03
 */
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
typedef  double ll;

const int maxn = 2e6+5;
int n,m;
bool vis[maxn];
int a[maxn];

//oisnip_begindfs-spfa-判断负环是否存在.cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3005;
const double INF = 1e9; 

// 邻接表存图 (目标点, 权值)
// 如果是 P3199 这种带参数的，权值计算可能在 dfs 内部动态算
struct Edge {
    int to;
    double w; 
};
vector<Edge> adj[MAXN];

// 建图辅助函数
void add_edge(int u, int v, double w) { adj[u].push_back({v, w}); }

double dis[MAXN];    // 记录距离
bool instack[MAXN];  // 【核心】记录当前递归栈中的节点 (是否是祖先)

// 【核心函数】DFS-SPFA
// u: 当前节点
// 返回值: true 表示发现负环, false 表示安全
bool spfa_dfs(int u, double x) {
    instack[u] = true; // 1. 入栈：标记 u 在当前路径上
    vis[u] = 1;

    for (auto &e : adj[u]) {
        int v = e.to;
        double w = e.w - x; 

        // 2. 松弛判断：只有能让距离变小，才继续走
        if (dis[v] > dis[u] + w) {
            dis[v] = dis[u] + w;

            // 3. 撞到祖先：如果 v 已经在栈里，说明在这个路径上绕回来了
            // 且满足松弛条件，说明环的权值和 < 0
            if (instack[v]) return true;

            // 4. 递归：继续往深处找，如果子路径发现环，直接上报
            if (spfa_dfs(v,x)) return true;
        }
    }

    instack[u] = false; // 5. 回溯：离开 u，出栈
    return false;
}


// 清空函数 (多测时使用)
void spfa_init(int _n) {
    n = _n;
    for (int i = 0; i <= n; i++) adj[i].clear();
}
//oisnip_end


void init(){
    std::cin >> n >> m;
    for(int i = 1;i <= m ;++i ) // i: 1->m
    {
        int u,v;
        double w;
        std::cin >> u >> v >> w;
        add_edge(u, v, w);
    }
}

bool check(double x) {

    // 初始化
    for (int i = 1; i <= n; i++) {
        dis[i] = 0;
        vis[i] = 0;
        instack[i] = false;
    }

    // 图是连通的
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        if( vis[i] ) continue;
        bool ret = spfa_dfs(i,x);
        if( ret ) return 1;
    }
    return 0;
}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    init();
    double l = -1e7, r = 1e7;

    for(int i = 1;i <= 70 ;++i ) // i: 1->709
    {
        double mid = (l+r) / 2;
        if( check(mid) )
            r = mid;
        else
            l = mid;
    }
    
    cout << fixed << setprecision(8) << l << endl;
    
    return 0;
}

5. 易错点与总结

为什么是 $w - x$ ？
- 不等式 $\sum w \le x \cdot k$ 移项得到 $\sum (w-x) \le 0$ 。这意味着每一条边的边权都要减去 $x$ 。
为什么用 DFS-SPFA？
- BFS-SPFA 判负环需要某个点入队次数达到 $N$ 次，效率较低，在二分内部跑容易超时。
- DFS-SPFA 只要在递归栈里撞到自己，就立刻抓住负环，效率极高。
dis 数组初始化：
- 这里不需要像求最短路那样初始化为 INF。因为我们是找负环，只要能不断变小（松弛）就行。把所有 dis 设为 0，相当于假设有一个虚拟源点连向所有点，边权为 0。

目录