用 min-plus 矩阵幂预处理好「最多 2^k 条边的最短路」,再按位从高到低贪心逼近最小负环边数,O(n^3 log n)。
OJ: roj
题目 ID: 1717
难度:提高+/省选-
标签:图论最短路倍增矩阵乘法python
创建: 2026-10-07 18:12
更新: 2026-10-07 18:12
形式化题目
给定
正解
思路
先解决"怎么判定负环"
常规的 Bellman-Ford / SPFA 判负环只回答"有没有",回答不了"最短的有多长"。但这题要的是最少点数,所以必须换一个能同时控制"边数"的判定工具。
关键是把判定条件改写成一句关于步数上界的陈述:
存在负环
存在某个 ,使得存在一条用不超过 条边的负权闭迹。
两个方向都要说清楚。
- 负环本身就是一条长度
的负权闭迹(简单环上点数不超过 ,而环的边数等于点数),所以右边成立。 - 反过来,若有一条
条边的负权闭迹,把它拆成若干个简单回路。若每个简单回路的权都非负,则闭迹总权非负,矛盾;所以其中至少有一个简单回路的权为负,即存在负环,且它的边数不超过 。
于是答案就是"存在负权闭迹的最小
用 min-plus 矩阵幂描述"不超过 L 条边的最短路"
把图写成邻接矩阵
定义 min-plus 乘法(也就是 Floyd 的矩阵形式)
它的含义是"先按
按位贪心定位最小 L
BITS = 8,
设 cur 表示"至多用 cur 为单位矩阵(只能原地不动)。从高位
- 试算
,它表示"至多用 条边"。 - 若
的主对角线没有负数,说明"至多 条边"里还没有负权闭迹,这一位可以安全地吃掉: cur = T,。 - 否则跳过这一位。
贪心的正确性来自
最后再乘一次
举个样例走一遍
样例是
四条边、四个点。用上面的倍增检查:
实现要点
- 主对角线始终
。这保证矩阵元素恒 :任何"至多 条边"的路径权值绝对值都不超过 ,两个 相加也不会溢出。用 long long+INF = 1e15是安全的(main.cpp里这么写);main.py用INF = 1 << 60。 - 不可达剪枝:
mul里若或 就直接跳过。这不只是常数优化:min-plus 乘法里 ,若不剪掉,会凭空造出"从不可达的点绕过去"的假路径,把答案算小。 main.py用向量式min(map(add, 行, 列))无法逐个跳过,因此对每个结果元素做夹回:只要求出的值超过就置回 (真实权值绝对值 ,夹不掉任何真值)。 - 注意原地踏步的语义:把主对角线置
之后,"闭迹"是允许在某点滞留的,但滞留不影响权值,所以"存在负闭迹"与"存在负环"仍然等价。
代码
#!/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()/**
* 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;
}复杂度
时间
main.py 只用标准库(oj-python-style 明确「不用第三方库」):内层用 min(map(add, 行, 列)) 把一个 oj-python-style 的约定(「允许 Python TLE/MLE,但绝不能因此把算法换成暴力枚举」)这是可接受的,正式提交请用 main.cpp(n=300 时 0.28 s)。
总结
这道题把"判定负环"从"能不能"升级成"最少多少条边",核心桥梁是把步数上限变成矩阵维度的语义:
- 主对角线置
,让"恰好 步"变成"至多 步",这是让矩阵幂能表达"不超过 条边的负闭迹"的关键一步。 - min-plus 乘法就是把"两段路拼起来",于是
可以倍增得到。 - 答案的二进制位可以逐位确定:每一步只需要一次乘法 + 一次主对角线符号检查。
它与经典的"二分 + 倍增"是同一思想的两种写法;按位贪心省掉一层
关于本题素材的说明
本题素材来自 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]= 恰好条边的最短路,逐层做一次 min-plus 乘法( cur = cur ⊗ A),检查最小的使主对角线出现负数;这就是"最短负环的边数",与按位贪心、倍增都无关。另外用 Bellman-Ford 单独判定"有没有负环"。 - 结论:10 个点的
.out全部与独立复核一致,没有出现 1421 那类"数据里藏着负环但.out是溢出回绕值"的情况。逐点结果如下。
| 数据点 | 规模 | .out |
独立复核 | 复核方法 |
|---|---|---|---|---|
| 1 | 0 | 无负环 | Bellman-Ford + exact- |
|
| 2 | 2 | 2 | exact- |
|
| 3 | 题面样例 |
4 | 4 | exact- |
| 4 | BZOJ 4773 样例 | 2 | 2 | exact- |
| 5 | 3 | 3 | exact- |
|
| 6 | 2 | 2 | exact- |
|
| 7 | 140 | 140 | exact- |
|
| 8 | 300 | 300 | exact- |
|
| 9 | 0 | 无负环 | Bellman-Ford + exact- |
|
| 10 | 257 | 257 | exact- |
对拍部分(main.cpp 与 main.py 同结果):小规模 main.py 最初少了"不可达时不能拿 main.cpp 因为提前 continue 而没有这个问题),现已修正,index.md 的代码片段即修正后的版本。
另外,题面描述段写的是"无向图",但输入段明确说"表示从 data.py 生成的数据也是按有向图理解的。