01 分数规划把平均权值最小化转成判负环,边权改成 w-λ 后多源 SPFA 二分出答案,无环单独判。
OJ: roj
题目 ID: 1720
难度:提高+/省选-
标签:图论二分答案01分数规划SPFA负环python
创建: 2026-10-07 18:13
更新: 2026-10-07 18:13
形式化题目
给定一张
其中
若图中不存在任何环,则输出固定字符串 PaPaFish is laying egg!;
否则输出该最小值,保留 2 位小数。
正解
思路
为什么不能枚举环。 环的数量可能是指数级的(
关键转化。 记答案为
于是
而
具有单调性:
判负环。 环权为负等价于"负环存在",标准做法是 SPFA:把 dis 全部初始化为 0
(相当于加一个到所有点都连 0 权边的虚拟源点),一次性把所有点压进队列。这样做有两个好处:
- 不要求图连通——孤立点、多个连通分量都能被照顾到;
- 起点权值就是 0,不需要对每个点各跑一次单源 SPFA。
负环的判据用最短路边数:松弛 cnt[v] = cnt[u] + 1。
若某个点的最短路已经走了
main.cpp 用的是上面这套 BFS 版多源 SPFA(写法接近网络题解的通行版本);
main.py 用的是语义等价的 DFS 版 SPFA:沿 DFS 栈松弛,若松弛到的点仍在当前
DFS 栈上,说明沿栈绕回了它,这段回路就是负环。两版判定的含义完全一致
(都是"以
无环必须单独判。 如果图本身无环,那么它当然没有负环,
二分的上下界。 因为
代码
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++ 版(同一算法):
/**
* 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;
}复杂度
- 时间:一次判环
;一次 SPFA 判负环最坏 ,但本题图上只有 1000 点、 10000 边,实测每次判定都在毫秒级(负环一旦存在通常很快就被命中)。 总复杂度 , 二分取 60(C++)/ 40(Python)次, 是上界而非实际值。 实测最坏点( 、 随机含环图):C++ 0.08 s,Python 0.04 s, 限时 1000 ms 下余量充足。 - 空间:链式前向星
,SPFA 辅助数组 dis / cnt / inq / que各, 总计 ;实测峰值内存 8.3 MB,远小于 128 MB。 - Python 侧:40 轮 SPFA 全部跑完的最坏点在 CPython 下约 0.04 s(DFS 版),
本机实测无 TLE 风险;若换成 BFS 版 SPFA 则会涨到约 1.4 s,故
main.py采用 DFS 版。 两版算法同阶,没有退化成暴力枚举环。
总结
- 比值最优 → 猜答案 + 判定:看到
(或本题的 ) 就应该想到 01 分数规划:二分 ,把判定条件整理成"某个和小于 0", 于是问题变成"以 为权的图是否存在负环"。 - 负环判定用多源 SPFA:
dis全 0 压入所有点,一次就能处理不连通图, 判据取"最短路边数",比"入队次数 "更稳。 - 特别小心"无解输出"的分支:判定函数单调的前提是"答案存在"。
无环时这个前提不成立,必须提前单独判掉,否则程序会安静地输出错误的
0.00。 - 二分界要贴合题面:因为
,下界天然是 0(而不是负无穷), 上界取最大边权就够——这两点都能从数据范围直接读出来。 - 同类题:UVA11090 Going in Cycle!!、BZOJ1486 / P3199《最小圈》, 与本题连"无解输出字符串"和样例都完全一致,是同一道题的不同改编版本。
关于本题素材的说明:本题随仓素材(
new_ROJ/problems/1720/)带有数据生成脚本data.py,说明data/的 10 个测试点是自行生成的,而非官方原题数据; 题面也可能来自网络重建,出题意图与官方原题可能存在偏差。 本解已用素材里的std.cpp(同样思路的 01 分数规划 + 多源 BFS-SPFA)跑过全部 10 个点, 两者输出逐点一致;又另写了一份"枚举全部简单环取平均权值最小"的暴力 对 950 组随机小图(,含 0 权边、自环、重边、顶格权值)做了对拍, C++、Python、暴力三方结果全部一致。