均值最小环

GitHub跳转原题关系图返回列表

01 分数规划把平均权值最小化转成判负环,边权改成 w-λ 后多源 SPFA 二分出答案,无环单独判。

OJ: roj

题目 ID: 1720

难度:提高+/省选-

标签:图论二分答案01分数规划SPFA负环python

创建: 2026-10-07 18:13

更新: 2026-10-07 18:13

形式化题目

给定一张 nn 个点、mm 条边的带权有向图,每条边 (u,v)(u, v) 有权值 wu,v⩾0w_{u,v} \geqslant 0 (允许自环、重边、零权边,边权均为整数且 0⩽w⩽1070 \leqslant w \leqslant 10^7)。 设图中的一个环为 CC,其平均权值定义为

avg(C)=∑e∈Cwe∣C∣,\mathrm{avg}(C) = \frac{\sum_{e \in C} w_e}{|C|},

其中 ∣C∣|C| 是环上的边数。要求写出

min⁡Cavg(C), \min_{C} \mathrm{avg}(C),

若图中不存在任何环,则输出固定字符串 PaPaFish is laying egg!; 否则输出该最小值,保留 2 位小数。

1⩽n⩽10001 \leqslant n \leqslant 1000,1⩽m⩽100001 \leqslant m \leqslant 10000。

正解

思路

为什么不能枚举环。 环的数量可能是指数级的(n=1000n = 1000、m=10000m = 10000 的稠密图里, 简单环的条数远超任何可以枚举的规模),把每个环算一遍平均权值是不可能的。 但题目只要最小值,而且目标函数 ∑w/∣C∣\sum w / |C| 是"分子 / 分母"的形式, 这类"比值最优"的问题有统一的处理套路:01 分数规划。

关键转化。 记答案为 ansans。对任意实数 λ\lambda,考虑把所有边权换成 we′=we−λw'_e = w_e - \lambda。 对某个环 CC:

∑e∈C(we−λ)<0  ⟺  ∑e∈Cwe<λ⋅∣C∣  ⟺  avg(C)<λ.\sum_{e \in C} (w_e - \lambda) < 0 \iff \sum_{e \in C} w_e < \lambda \cdot |C| \iff \mathrm{avg}(C) < \lambda .

于是

∃ 环 C: avg(C)<λ  ⟺  图上(以 we−λ 为权)存在负环. \exists \text{ 环 } C:\ \mathrm{avg}(C) < \lambda \iff \text{图上(以 } w_e - \lambda \text{ 为权)存在负环} .

而 ∃C:avg(C)<λ  ⟺  ans<λ\exists C: \mathrm{avg}(C) < \lambda \iff ans < \lambda。所以判定函数

f(λ)=[边权换成 we−λ 后存在负环]f(\lambda) = [\text{边权换成 } w_e - \lambda \text{ 后存在负环}]

具有单调性:f(λ)=true  ⟺  λ>ansf(\lambda) = \text{true} \iff \lambda > ans。二分 λ\lambda,就能把 ansans 逼到任意精度。 这就是本题的全部主体。

判负环。 环权为负等价于"负环存在",标准做法是 SPFA:把 dis 全部初始化为 0 (相当于加一个到所有点都连 0 权边的虚拟源点),一次性把所有点压进队列。这样做有两个好处:

  1. 不要求图连通——孤立点、多个连通分量都能被照顾到;
  2. 起点权值就是 0,不需要对每个点各跑一次单源 SPFA。

负环的判据用最短路边数:松弛 u→vu \to v 时令 cnt[v] = cnt[u] + 1。 若某个点的最短路已经走了 ⩾n\geqslant n 条边,这条路径上的 n+1n+1 个顶点必有重复, 删掉中间那段回路后权值不增,因此那个回路就是负环。反之,若没有负环, 任何最短路的边数都不会超过 n−1n - 1(否则可以取更短的路),判据不会误报。

main.cpp 用的是上面这套 BFS 版多源 SPFA(写法接近网络题解的通行版本); main.py 用的是语义等价的 DFS 版 SPFA:沿 DFS 栈松弛,若松弛到的点仍在当前 DFS 栈上,说明沿栈绕回了它,这段回路就是负环。两版判定的含义完全一致 (都是"以 we−λw_e - \lambda 为权的图有无负环"),只是入队开销不同; DFS 版在 Python 里常数小一个量级,n=1000,m=10000n=1000, m=10000 的最坏点从 1.4 s 降到 0.04 s。

无环必须单独判。 如果图本身无环,那么它当然没有负环,f(λ)f(\lambda) 恒为 false, 二分会把答案压成 0.000.00 输出出来——这是错的,题面要求输出那一串固定字符串。 所以正式流程先做一次精确判环(DFS 三色标记,迭代版避免爆递归深度), 无环则直接返回。等价说法是:判 λ=107+10\lambda = 10^7 + 10 是否仍有负环, 但显式判环更快、语义也更直白。

二分的上下界。 因为 we⩾0w_e \geqslant 0,任何环的平均权值 ⩾0\geqslant 0,故下界取 00; 又因为任意环的平均权值不超过它的最大边权,故上界取 maxw=max⁡ewemaxw = \max_e w_e。 迭代 60 次后区间长度 107/260≈10−1110^7 / 2^{60} \approx 10^{-11},远小于 10−210^{-2} 的精度需求。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 18:13
# update_at: 2026-10-07 18:13

import sys

NO_CYCLE = "PaPaFish is laying egg!"  # 无环时的固定输出
BINARY_STEPS = 40                     # 二分次数:区间 1e7 / 2^40 << 0.005,足够定出两位小数

type Edges = list[tuple[int, int, int]]   # 每条边 (u, v, w),点从 1 开始编号
type Adj = list[list[tuple[int, int]]]    # 邻接表:adj[u] = [(v, w), ...]


def build_adj(n: int, edges: Edges) -> Adj:
    """把边表转成邻接表,adj[u] 存 u 的所有出边。"""
    adj: Adj = [[] for _ in range(n + 1)]
    for u, v, w in edges:
        adj[u].append((v, w))
    return adj


def has_cycle(n: int, adj: Adj) -> bool:
    """有向图是否有环:三色标记迭代 DFS,0 未访问 / 1 在栈上 / 2 已完成。"""
    color = [0] * (n + 1)
    for s in range(1, n + 1):
        if color[s]:
            continue
        color[s] = 1
        stack = [(s, iter(adj[s]))]              # (顶点, 尚未枚举完的出边迭代器)
        while stack:
            u, it = stack[-1]
            nxt = next(it, None)
            if nxt is None:                      # u 的出边枚举完了
                color[u] = 2
                stack.pop()
            elif color[nxt[0]] == 1:             # 指向栈上的点 ⇒ 有环
                return True
            elif color[nxt[0]] == 0:
                color[nxt[0]] = 1
                stack.append((nxt[0], iter(adj[nxt[0]])))
    return False


def has_negative_cycle(n: int, adj: Adj, lam: float) -> bool:
    """边权换成 w - lam 后是否存在负环(DFS 版 SPFA)。

    dis 全部初始化为 0,相当于加一个 0 权虚拟源点连到所有点,因此不要求图连通。
    松弛 u->v 时若 v 正处在当前 DFS 栈上,说明沿栈走回了 v,这段回路权值为负;
    若 v 不在栈上则带着更小的 dis[v] 继续深入。DFS 版比 BFS 版少一半入队开销,
    Python 下常数小得多;判定语义与 C++ 版的多源 BFS-SPFA 完全一致。
    """
    dis = [0.0] * (n + 1)
    on_stack = bytearray(n + 1)
    for s in range(1, n + 1):
        if on_stack[s]:
            continue
        on_stack[s] = 1
        stack = [(s, iter(adj[s]))]
        while stack:
            u, it = stack[-1]
            nxt = next(it, None)
            if nxt is None:                      # u 的出边枚举完,离开 DFS 栈
                on_stack[u] = 0
                stack.pop()
                continue
            v, w = nxt
            nd = dis[u] + w - lam
            if nd < dis[v] - 1e-12:
                dis[v] = nd
                if on_stack[v]:                  # 回到栈上的点 ⇒ 存在负环
                    return True
                on_stack[v] = 1
                stack.append((v, iter(adj[v])))
    return False


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    edges: Edges = [(next(data), next(data), next(data)) for _ in range(m)]

    adj = build_adj(n, edges)
    if not has_cycle(n, adj):                    # 无环分支先判掉,否则二分结果无意义
        print(NO_CYCLE)
        return

    maxw = max(w for _, _, w in edges)           # 答案一定不超过最大边权(0 <= w)
    lo, hi = 0.0, float(maxw)
    for _ in range(BINARY_STEPS):
        mid = (lo + hi) / 2
        if has_negative_cycle(n, adj, mid):      # 存在负环 ⇒ 答案 <= mid
            hi = mid
        else:
            lo = mid
    print(f"{(lo + hi) / 2:.2f}")


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 18:13
 * update_at: 2026-10-07 18:13
 */

// 一本通 1720《均值最小环》:求带权有向图中所有环的"平均边权"最小值,无环输出约定字符串。
//
// 做法:01 分数规划 + 二分答案 + SPFA 判负环(同 UVA11090 / BZOJ1486 / P3199)。
//   * 二分 λ:把每条边权改成 w - λ,图中存在负环 ⟺ 存在环使 Σw/len < λ,即 λ 偏大。
//   * 判负环用多源 SPFA:dis[] 全 0(等价加一个到所有点的 0 权虚拟源),图可以不连通;
//     用"最短路边数 >= n 必有重复顶点 ⇒ 该回路为负"来判定。
//   * 无环要先精确判掉(DFS 三色标记),否则二分在无环图上永远判不出负环,
//     会把答案当成 0.00 输出,与约定的 "PaPaFish is laying egg!" 不符。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1005;    // 点数上限 1000
const int MAXM = 10005;   // 边数上限 10000
const double EPS = 1e-12; // 浮点比较容差

// 链式前向星:head[u] 为 u 的第一条出边编号,0 表示没有出边
int head[MAXN];
int nxt[MAXM];
int to_[MAXM];
ll wt[MAXM];   // 边权,题面 0 <= w <= 1e7,用 ll 存
int eid;       // 已分配的边编号

ll n, m;       // 点数和边数

// 加一条 u -> v 权值为 w 的有向边
void add_edge(ll u, ll v, ll w) {
    eid++;
    to_[eid] = v;
    wt[eid] = w;
    nxt[eid] = head[u];
    head[u] = eid;
}

// 三色标记判环:0 = 未访问,1 = 在当前 DFS 栈上,2 = 已完成
int color[MAXN];
int stk_v[MAXN];  // 迭代版 DFS 的顶点栈
int stk_e[MAXN];  // 迭代版 DFS 的"下一条待枚举出边"栈

// 图中是否存在环(迭代 DFS,避免 n=1000 递归深度问题)
bool has_cycle() {
    for (int i = 1; i <= n; i++) color[i] = 0;
    for (int s = 1; s <= n; s++) {
        if (color[s] != 0) continue;
        int top = 0;
        stk_v[0] = s;
        stk_e[0] = head[s];
        color[s] = 1;
        while (top >= 0) {
            int u = stk_v[top];
            int e = stk_e[top];
            if (e == 0) {          // u 的出边枚举完了,u 成为已完成点
                color[u] = 2;
                top--;
                continue;
            }
            stk_e[top] = nxt[e];   // 先把下一条出边记下,再决定是否深入
            int v = to_[e];
            if (color[v] == 1) return true;  // 指向栈上的点 ⇒ 有环
            if (color[v] == 0) {
                color[v] = 1;
                top++;
                stk_v[top] = v;
                stk_e[top] = head[v];
            }
        }
    }
    return false;
}

// SPFA 判负环用:dis[i] = 虚拟源点到 i 的当前最短距离,cnt[i] = 该最短路的边数
double dis[MAXN];
int cnt[MAXN];
char inq[MAXN];           // 是否在队列中,只有 0/1,用 char 省内存
int que[MAXN * 128];      // 手写循环队列,容量按最坏入队次数放大

// 把每条边权改成 w - lambda 后,图中是否存在负环
bool has_negative_cycle(double lambda) {
    int qh = 0, qt = 0;
    for (int i = 1; i <= n; i++) {
        dis[i] = 0.0;         // 多源起点:等价于虚拟源点连 0 权边到每个点
        cnt[i] = 0;
        inq[i] = 1;
        que[qt++] = i;
    }
    while (qh < qt) {
        int u = que[qh++];
        inq[u] = 0;
        for (int e = head[u]; e != 0; e = nxt[e]) {
            int v = to_[e];
            double nd = dis[u] + (double)wt[e] - lambda;
            if (nd < dis[v] - EPS) {
                dis[v] = nd;
                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= n) return true;  // 最短路用了 >= n 条边 ⇒ 绕出了负环
                if (!inq[v]) {
                    inq[v] = 1;
                    que[qt++] = v;
                }
            }
        }
        if (qt > MAXN * 128 - MAXN - 5) {  // 队列吃紧就整体前移,正常不会走到
            int k = 0;
            for (int i = qh; i < qt; i++) que[k++] = que[i];
            qh = 0;
            qt = k;
        }
    }
    return false;
}

// 读入一个整数(题面全为非负整数,负数只是容错)
ll read_int() {
    int c = getchar();
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    ll sgn = 1;
    if (c == '-') {
        sgn = -1;
        c = getchar();
    }
    ll x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar();
    }
    return sgn * x;
}

int main() {
    n = read_int();
    m = read_int();

    ll maxw = 0;   // 答案的上界:最小平均环的平均值一定不超过最大边权
    for (ll i = 0; i < m; i++) {
        ll u = read_int(), v = read_int(), w = read_int();
        add_edge(u, v, w);
        if (w > maxw) maxw = w;
    }

    if (!has_cycle()) {   // ① 无环:输出约定字符串
        printf("PaPaFish is laying egg!\n");
        return 0;
    }

    // ② 01 分数规划:答案 ans ∈ [0, maxw],二分找最小的"存在负环"的 λ
    double lo = 0.0, hi = (double)maxw;
    for (int it = 0; it < 60; it++) {
        double mid = (lo + hi) * 0.5;
        if (has_negative_cycle(mid)) hi = mid;  // 存在负环 ⇒ ans <= mid
        else lo = mid;
    }
    printf("%.2f\n", (lo + hi) * 0.5);
    return 0;
}

复杂度

  • 时间:一次判环 O(n+m)O(n + m);一次 SPFA 判负环最坏 O(nm)O(nm),但本题图上只有 1000 点、 10000 边,实测每次判定都在毫秒级(负环一旦存在通常很快就被命中)。 总复杂度 O((n+m)+log⁡(maxwε)⋅nm)O\big((n + m) + \log(\frac{maxw}{\varepsilon}) \cdot nm\big), 二分取 60(C++)/ 40(Python)次,nm=107nm = 10^7 是上界而非实际值。 实测最坏点(n=1000n=1000、m=10000m=10000 随机含环图):C++ 0.08 s,Python 0.04 s, 限时 1000 ms 下余量充足。
  • 空间:链式前向星 O(n+m)O(n + m),SPFA 辅助数组 dis / cnt / inq / que 各 O(n)O(n), 总计 O(n+m)O(n + m);实测峰值内存 8.3 MB,远小于 128 MB。
  • Python 侧:40 轮 SPFA 全部跑完的最坏点在 CPython 下约 0.04 s(DFS 版), 本机实测无 TLE 风险;若换成 BFS 版 SPFA 则会涨到约 1.4 s,故 main.py 采用 DFS 版。 两版算法同阶,没有退化成暴力枚举环。

总结

  • 比值最优 → 猜答案 + 判定:看到 min⁡∑a/∑b\min \sum a / \sum b(或本题的 ∑w/∣C∣\sum w / |C|) 就应该想到 01 分数规划:二分 λ\lambda,把判定条件整理成"某个和小于 0", 于是问题变成"以 we−λw_e - \lambda 为权的图是否存在负环"。
  • 负环判定用多源 SPFA:dis 全 0 压入所有点,一次就能处理不连通图, 判据取"最短路边数 ⩾n\geqslant n",比"入队次数 ⩾n\geqslant n"更稳。
  • 特别小心"无解输出"的分支:判定函数单调的前提是"答案存在"。 无环时这个前提不成立,必须提前单独判掉,否则程序会安静地输出错误的 0.00。
  • 二分界要贴合题面:因为 w⩾0w \geqslant 0,下界天然是 0(而不是负无穷), 上界取最大边权就够——这两点都能从数据范围直接读出来。
  • 同类题:UVA11090 Going in Cycle!!、BZOJ1486 / P3199《最小圈》, 与本题连"无解输出字符串"和样例都完全一致,是同一道题的不同改编版本。

关于本题素材的说明:本题随仓素材(new_ROJ/problems/1720/)带有数据生成脚本 data.py,说明 data/ 的 10 个测试点是自行生成的,而非官方原题数据; 题面也可能来自网络重建,出题意图与官方原题可能存在偏差。 本解已用素材里的 std.cpp(同样思路的 01 分数规划 + 多源 BFS-SPFA)跑过全部 10 个点, 两者输出逐点一致;又另写了一份"枚举全部简单环取平均权值最小"的暴力 对 950 组随机小图(n⩽11n \leqslant 11,含 0 权边、自环、重边、顶格权值)做了对拍, C++、Python、暴力三方结果全部一致。