负环

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

用 min-plus 矩阵幂预处理好「最多 2^k 条边的最短路」,再按位从高到低贪心逼近最小负环边数,O(n^3 log n)。

OJ: roj

题目 ID: 1717

难度:提高+/省选-

标签:图论最短路倍增矩阵乘法python

创建: 2026-10-07 18:12

更新: 2026-10-07 18:12

形式化题目

给定 nn 个点、mm 条边的带权有向图,无重边、无自环(题面描述段写"无向图",但输入段与样例都明确是"从 uiu_i 到 viv_i 的有向边",以输入段为准)。求一个点数最少的环,使环上边权和为负;不存在这样的环则输出 00。

2⩽n⩽3002 \leqslant n \leqslant 300,0⩽m⩽n(n−1)0 \leqslant m \leqslant n(n-1),∣wi∣⩽104|w_i| \leqslant 10^4。

正解

思路

先解决"怎么判定负环"

常规的 Bellman-Ford / SPFA 判负环只回答"有没有",回答不了"最短的有多长"。但这题要的是最少点数,所以必须换一个能同时控制"边数"的判定工具。

关键是把判定条件改写成一句关于步数上界的陈述:

存在负环   ⟺  \iff 存在某个 L⩽nL \leqslant n,使得存在一条用不超过 LL 条边的负权闭迹。

两个方向都要说清楚。

  • 负环本身就是一条长度 ⩽n\leqslant n 的负权闭迹(简单环上点数不超过 nn,而环的边数等于点数),所以右边成立。
  • 反过来,若有一条 ⩽L\leqslant L 条边的负权闭迹,把它拆成若干个简单回路。若每个简单回路的权都非负,则闭迹总权非负,矛盾;所以其中至少有一个简单回路的权为负,即存在负环,且它的边数不超过 LL。

于是答案就是"存在负权闭迹的最小 LL",记作 L∗L^*;不存在负环时输出 00。注意闭迹允许重复经过点,所以它是简单环的宽松版本——正是这个宽松让它可以被矩阵幂描述。

用 min-plus 矩阵幂描述"不超过 L 条边的最短路"

把图写成邻接矩阵 AA,并把主对角线改成 00:Aii=0A_{ii} = 0 表示"停在原地不动",代价为 00。这个约定把"恰好用 kk 条边"松弛成"至多用 kk 条边"——因为原地踏步不花钱,走不满的边数可以用自环补足。

定义 min-plus 乘法(也就是 Floyd 的矩阵形式)

(X⊗Y)ij=min⁡k(Xik+Ykj),(X \otimes Y)_{ij} = \min_k \left(X_{ik} + Y_{kj}\right),

它的含义是"先按 XX 走一段、再按 YY 走一段"。用 pw[k]\mathrm{pw}[k] 表示"至多用 2k2^k 条边"时任意两点间的最小权值和,则

pw[0]=A,pw[k]=pw[k−1]⊗pw[k−1].\mathrm{pw}[0] = A, \qquad \mathrm{pw}[k] = \mathrm{pw}[k-1] \otimes \mathrm{pw}[k-1].

pw[k]\mathrm{pw}[k] 的主对角线 (pw[k])ii(\mathrm{pw}[k])_{ii} 就是"从 ii 出发、不超过 2k2^k 条边回到 ii 的最小权值"。只要它出现负数,就说明存在边数不超过 2k2^k 的负权闭迹,进而存在负环。

按位贪心定位最小 L

L∗⩽n⩽300<511=29−1L^* \leqslant n \leqslant 300 < 511 = 2^9 - 1,所以取 k=0…8k = 0 \ldots 8 共 9 层就够(BITS = 8,28=2562^8 = 256,加上贪心累加能表示到 511511)。

设 cur 表示"至多用 tot\mathrm{tot} 条边"的最短路矩阵,初始 tot=0\mathrm{tot} = 0、cur 为单位矩阵(只能原地不动)。从高位 kk 往低位扫:

  1. 试算 T=cur⊗pw[k]T = \mathrm{cur} \otimes \mathrm{pw}[k],它表示"至多用 tot+2k\mathrm{tot} + 2^k 条边"。
  2. 若 TT 的主对角线没有负数,说明"至多 tot+2k\mathrm{tot} + 2^k 条边"里还没有负权闭迹,这一位可以安全地吃掉:cur = T,tot+=2k\mathrm{tot} \mathrel{+}= 2^k。
  3. 否则跳过这一位。

贪心的正确性来自 L∗L^* 的二进制分解:如果 tot\mathrm{tot} 的已定高位与 L∗L^* 一致,而 tot+2k<L∗\mathrm{tot} + 2^k < L^*,那么第 2 步的条件必然成立(还没到 L∗L^* 就没有负闭迹);反之若 tot+2k⩾L∗\mathrm{tot} + 2^k \geqslant L^*,条件必然不成立(已经越过 L∗L^*)。所以每一位的判定都与 L∗L^* 的该位一致,循环结束后 tot=L∗−1\mathrm{tot} = L^* - 1。

最后再乘一次 pw[0]\mathrm{pw}[0](只允许"一条边"这一层),主对角线出现负数就输出 tot+1\mathrm{tot} + 1,否则输出 00(此时 tot\mathrm{tot} 已经涨到 511511,等价于"图里根本没有负环")。

举个样例走一遍

样例是 n=4n = 4、m=8m = 8,答案为 44。把边按题意连上后,唯一能形成负环的是 1→3→4→2→11 \to 3 \to 4 \to 2 \to 1:

(−1)+0+1+(−3)=−3<0,(-1) + 0 + 1 + (-3) = -3 < 0,

四条边、四个点。用上面的倍增检查:pw[2]\mathrm{pw}[2](不超过 44 条边)的主对角线已经出现 −3-3,而贪心会在更高位先探路,最终定位到 tot=3\mathrm{tot} = 3,输出 44。

实现要点

  • 主对角线始终 ⩽0\leqslant 0。这保证矩阵元素恒 ⩽INF\leqslant \mathrm{INF}:任何"至多 511511 条边"的路径权值绝对值都不超过 511×104511 \times 10^4,两个 INF\mathrm{INF} 相加也不会溢出。用 long long + INF = 1e15 是安全的(main.cpp 里这么写);main.py 用 INF = 1 << 60。
  • 不可达剪枝:mul 里若 aik=INFa_{ik} = \mathrm{INF} 或 bkj=INFb_{kj} = \mathrm{INF} 就直接跳过。这不只是常数优化:min-plus 乘法里 INF+(−104)<INF\mathrm{INF} + (-10^4) < \mathrm{INF},若不剪掉,会凭空造出"从不可达的点绕过去"的假路径,把答案算小。main.py 用向量式 min(map(add, 行, 列)) 无法逐个跳过,因此对每个结果元素做夹回:只要求出的值超过 INF/2\mathrm{INF}/2 就置回 INF\mathrm{INF}(真实权值绝对值 <511×104≪INF/2< 511 \times 10^4 \ll \mathrm{INF}/2,夹不掉任何真值)。
  • 注意原地踏步的语义:把主对角线置 00 之后,"闭迹"是允许在某点滞留的,但滞留不影响权值,所以"存在负闭迹"与"存在负环"仍然等价。

代码

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:08
# update_at: 2026-10-07 18:35

# 倍增 Floyd(min-plus 矩阵幂)+ 按位贪心。
# 只依赖标准库;n=300 时一次乘法是 3e7 次加法,纯 Python 会 TLE,
# 但算法与 C++ 同阶(没有降级成暴力),按 oj-python-style 的约定可以接受。
# 正式提交请用 main.cpp。

import sys
from operator import add

INF = 1 << 60  # 路径权值绝对值 < 511 * 1e4,用大整数当无穷,两两相加也不会溢出
BITS = 8       # 倍增层数:2^8 = 256 > n,配合按位贪心足以覆盖 0..511 条边

type Mat = list[list[int]]  # n×n 权值和矩阵,mat[i][j] = i 到 j 的最小权值和


def min_plus(a: Mat, b: Mat) -> Mat:
    """min-plus 乘法 c[i][j] = min_k a[i][k] + b[k][j]:先走 a 的一段再走 b 的一段。"""
    cols = list(zip(*b))  # 按列取,让内层能用 map(add, 行, 列) 一次算完
    half = INF // 2
    return [
        # a[i][k] = INF 配上一个负的 b[k][j] 会算出 INF + w < INF 的假路径,夹回 INF。
        # 真实路径权值绝对值远小于 INF // 2,夹不掉任何真值。
        [INF if (v := min(map(add, row, col))) > half else v for col in cols]
        for row in a
    ]


def has_negative_diag(a: Mat) -> bool:
    """主对角线出现负数,就说明存在负权闭迹,等价于存在负环。"""
    return any(a[i][i] < 0 for i in range(len(a)))


def doubled_powers(base: Mat) -> list[Mat]:
    """pw[k] = 「最多用 2^k 条边」的最小权值和;pw[0] 就是 base。"""
    pw = [base]
    for _ in range(BITS):
        pw.append(min_plus(pw[-1], pw[-1]))  # 把同一段路走两遍
    return pw


def smallest_negative_cycle(powers: list[Mat]) -> int:
    """最短负环的边数,无负环返回 0。

    按位从高位到低位定答案:cur 表示「至多 tot 条边」的最短路,
    若 cur ⊗ powers[k] 的主对角线没有负数,说明还没越过答案,这一位可以吃掉。
    """
    n = len(powers[0])
    cur = [[0 if i == j else INF for j in range(n)] for i in range(n)]  # 至多 0 条边 = 停在原地
    tot = 0
    for k in range(BITS, -1, -1):
        nxt = min_plus(cur, powers[k])
        if not has_negative_diag(nxt):
            cur, tot = nxt, tot + (1 << k)
    return tot + 1 if has_negative_diag(min_plus(cur, powers[0])) else 0


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    # base = pw[0]:最多用 1 条边(对角线为 0,表示「停在原地」)
    base = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    for _ in range(m):
        u, v, w = next(data), next(data), next(data)
        base[u - 1][v - 1] = w  # 题面保证无重边

    print(smallest_negative_cycle(doubled_powers(base)))


if __name__ == "__main__":
    solve()
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:08
 * update_at: 2026-10-07 18:12
 */

// 一本通 1717《负环》
// 题意:n 个点 m 条边、无重边无自环的带权有向图,求点数最少的负环含几个点;没有负环输出 0。
//
// 做法:倍增 Floyd(min-plus 矩阵幂)+ 按位贪心,O(n^3 log n)。
//   设 pw[k][i][j] = 从 i 到 j、最多用 2^k 条边的最小权值和(允许停在原地,即主对角线为 0)。
//   于是 pw[0] 是邻接矩阵(对角线改成 0),pw[k] = pw[k-1] (x) pw[k-1],
//   其中 (x) 是 min-plus 乘法,也就是把“前半段 + 后半段”拼起来取最小值。
//   负环一定以简单环形式出现,最长不超过 n <= 300 条边,所以 9 个二进制位(最大 511 条边)够用。
//   按位从高到低贪心:cur 表示“最多 tot 条边”的最短路矩阵,
//   若 cur (x) pw[k] 的主对角线全非负(说明不存在 <= tot + 2^k 条边的负权闭迹),
//   就接受这一位:cur = cur (x) pw[k],tot += 2^k;否则跳过。
//   循环结束时再乘一次 pw[0](一条边):主对角线出现负数就说明最小负环长度是 tot + 1,否则输出 0。
//
// 关键点:
//   - “存在负权闭迹”等价于“存在负环”(闭迹删掉非负的子回路后必然剩下负环),
//     所以答案就是“存在 <= L 条边的负权闭迹”里最小的那个 L。
//   - 主对角线恒 <= 0,于是所有矩阵元素 <= INF,且真实路径权值绝对值 <= 511 * 10^4 < INF。

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

typedef long long ll;

const int MAXN = 305;     // 点数上限 300,多开几格防越界
const int MAXB = 8;       // 倍增层数:2^8 = 256,配合按位贪心可表示 0..511 条边
const ll INF = 1000000000000000LL;  // 远大于任何真实路径权值,且两个 INF 相加也不会溢出

int n, m;                     // n 点数,m 边数
ll pw[MAXB + 1][MAXN][MAXN];  // pw[k][i][j]:i 到 j 最多用 2^k 条边的最小权值和
ll cur[MAXN][MAXN];           // 至多 tot 条边的最小权值和矩阵
ll nxt[MAXN][MAXN];           // 一次乘法后的临时结果

// out = a (x) b:min-plus 乘法,含义是“先走 a 的一段、再走 b 的一段”
void mul(const ll a[][MAXN], const ll b[][MAXN], ll out[][MAXN])
{
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) out[i][j] = INF;
        for (int k = 0; k < n; ++k) {
            if (a[i][k] >= INF) continue;  // 不可达的中间点直接跳过,省一半时间
            for (int j = 0; j < n; ++j) {
                if (b[k][j] >= INF) continue;  // 后半段不可达,不能拿 INF 减权值凑出假路径
                ll v = a[i][k] + b[k][j];
                if (v < out[i][j]) out[i][j] = v;
            }
        }
    }
}

// 主对角线上是否有负数:有就说明存在负权闭迹(等价于存在负环)
bool has_neg_diag(const ll a[][MAXN])
{
    for (int i = 0; i < n; ++i)
        if (a[i][i] < 0) return true;
    return false;
}

int main()
{
    if (scanf("%d %d", &n, &m) != 2) return 0;

    // pw[0]:一条边(或原地不动,权值 0)
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) pw[0][i][j] = INF;
    for (int i = 0; i < n; ++i) pw[0][i][i] = 0;
    for (int e = 0; e < m; ++e) {
        int u, v;
        ll w;
        if (scanf("%d %d %lld", &u, &v, &w) != 3) return 0;
        --u;
        --v;
        if (w < pw[0][u][v]) pw[0][u][v] = w;  // 题面保证无重边,这里只作防御
    }

    // 倍增预处理:pw[k] = pw[k-1] 走两遍
    for (int k = 1; k <= MAXB; ++k) mul(pw[k - 1], pw[k - 1], pw[k]);

    // cur 初值 = “至多 0 条边” = 单位矩阵(只能原地不动)
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) cur[i][j] = (i == j ? 0 : INF);

    int tot = 0;  // 已经确认“不存在 <= tot 条边的负环”
    for (int k = MAXB; k >= 0; --k) {
        mul(cur, pw[k], nxt);
        if (!has_neg_diag(nxt)) {  // 这一段可以安全接受
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j) cur[i][j] = nxt[i][j];
            tot += 1 << k;
        }
    }

    mul(cur, pw[0], nxt);
    printf("%d\n", has_neg_diag(nxt) ? tot + 1 : 0);
    return 0;
}

复杂度

时间 O(n3log⁡n)O(n^3 \log n):预处理 99 次 min-plus 乘法,贪心 99 次,共 1818 次 O(n3)O(n^3);n=300n = 300 时约 5×1085 \times 10^8 次加法,C++ 在 2s 内可过(含不可达剪枝后实际更快)。空间 O(n2log⁡n)O(n^2 \log n),存 99 个矩阵,n=300n = 300 时约 2.62.6 MB。

main.py 只用标准库(oj-python-style 明确「不用第三方库」):内层用 min(map(add, 行, 列)) 把一个 300×300300 \times 300 的乘法压到 99 万个 C 层调用上,而不是 99 万个纯 Python 循环。算法与 C++ 完全同阶,没有降级成暴力。代价是常数:实测 n=300 时单点 8.6–11.8 s,超过 1000 ms 限,Python 版在大点会 TLE——按 oj-python-style 的约定(「允许 Python TLE/MLE,但绝不能因此把算法换成暴力枚举」)这是可接受的,正式提交请用 main.cpp(n=300 时 0.28 s)。

总结

这道题把"判定负环"从"能不能"升级成"最少多少条边",核心桥梁是把步数上限变成矩阵维度的语义:

  1. 主对角线置 00,让"恰好 kk 步"变成"至多 kk 步",这是让矩阵幂能表达"不超过 LL 条边的负闭迹"的关键一步。
  2. min-plus 乘法就是把"两段路拼起来",于是 pw[k]\mathrm{pw}[k] 可以倍增得到。
  3. 答案的二进制位可以逐位确定:每一步只需要一次乘法 + 一次主对角线符号检查。

它与经典的"二分 + 倍增"是同一思想的两种写法;按位贪心省掉一层 log⁡\log 的外层二分,代码更短,也是 BZOJ 4773《负环》的常见做法。

关于本题素材的说明

本题素材来自 new_ROJ/problems/1717/,目录里带 data.py 生成脚本,说明 data/ 是自造的、content.md 也是网络重建的题面(与 BZOJ 4773《负环》的题面、数据范围一致)。因此 data/*.out 是由同目录 std.cpp 生成的,不是官方数据。std.cpp 的做法(倍增 Floyd + 按位贪心)与题面自洽,我没有发现它算错;但为了不盲信 .out,我用与 std.cpp 不同的方法独立复核了每个点:

  • 复核方法:dp_k[i][j] = 恰好 kk 条边的最短路,逐层做一次 min-plus 乘法(cur = cur ⊗ A),检查最小的 kk 使主对角线出现负数;这就是"最短负环的边数",与按位贪心、倍增都无关。另外用 Bellman-Ford 单独判定"有没有负环"。
  • 结论:10 个点的 .out 全部与独立复核一致,没有出现 1421 那类"数据里藏着负环但 .out 是溢出回绕值"的情况。逐点结果如下。
数据点 规模 .out 独立复核 复核方法
1 n=2,m=0n=2, m=0 0 无负环 Bellman-Ford + exact-kk
2 n=2,m=2n=2, m=2 2 2 exact-kk
3 题面样例 n=4,m=8n=4,m=8 4 4 exact-kk
4 BZOJ 4773 样例 2 2 exact-kk
5 n=7,m=10n=7, m=10 3 3 exact-kk
6 n=150,m=2000n=150, m=2000 2 2 exact-kk
7 n=150n=150,植入 140 边负环 140 140 exact-kk
8 n=300n=300,唯一 300 边负环 300 300 exact-kk
9 n=300n=300 全正权完全图 0 无负环 Bellman-Ford + exact-kk
10 n=300n=300,257 边负环(-1/边) 257 257 exact-kk

对拍部分(main.cpp 与 main.py 同结果):小规模 n⩽8n \leqslant 8 枚举所有简单环的暴力 400 组、中规模 n⩽40n \leqslant 40 的 exact-kk 参照 120 组、植入 2∼3002 \sim 300 边长负环的位边界用例 40 组,全部一致。这些对拍还揪出了一个真实 bug:main.py 最初少了"不可达时不能拿 INF\mathrm{INF} 减权值"的夹回保护(main.cpp 因为提前 continue 而没有这个问题),现已修正,index.md 的代码片段即修正后的版本。

另外,题面描述段写的是"无向图",但输入段明确说"表示从 uiu_i 到 viv_i 权值为 wiw_i 的有向边",样例也只有在有向语义下才成立(答案 4 对应 1→3→4→2→11 \to 3 \to 4 \to 2 \to 1)。我按有向图实现;data.py 生成的数据也是按有向图理解的。