把月度收入换成前缀和 s[i],每条记录即 s[y]-s[x-1]=w;等式组化成差分约束判负环(带权并查集同样可判),矛盾则输出 false。
OJ: roj
题目 ID: 1725
难度:提高+/省选-
标签:图论差分约束并查集负环python
创建: 2026-10-07 18:56
更新: 2026-10-07 18:56
形式化题目
有一个长度为
的信息,其中 true(存在)或 false(不存在)。
数据范围:
关键的量只有「区间和」,而区间和可以互相加减。以样例的两组数据为例:
| 组 | 信息 | 从信息推出的关系 | 结论 |
|---|---|---|---|
| 1 | 前两条给出 |
true |
|
| 2 | 两条路算出 |
false |
(表中
正解
思路
第一步:把区间和换成前缀和。
设
一条信息
这一步为什么有用?直接对
还要确认:
第二步:等式组转成差分约束图。
把每个等式 (1) 拆成两条不等式:
这两条不等式同时成立就等价于等式成立。于是把
| 不等式 | 有向边 |
|---|---|
第三步:无负环
差分约束系统的标准结论:不等式组
- 若有负环
,把环上不等式逐条相加得到 ,矛盾,无解。 - 若无负环,就取
为源点到 的最短路长度,则对每条边 都有 (最短路的三角不等式),是一组解。
第四步:为什么整数解等价于实数解。
上面的构造用最短路给出解,而本题所有边权
第五步:怎么判负环。
结点数
- 规模下
, 组总计 ,远够用; - Bellman-Ford 是确定性的,不会被 SPFA 的随机化数据卡掉。
实现上有个小技巧:直接把 dist[] 全部初始化为
等价视角:带权并查集。
等式组还有另一条更快的路。把 (1) 式看成"
- 若
与 已在同一集合,读出两者与根的差相减, 得到已有的 ,与 不符就矛盾; - 否则合并两棵树,把被挂上去的根的势设成
,使等式成立。
它和负环判定是同一件事:合并冲突
本文给出两份代码,正是同一模型的两条落地路线:
- C++ 版:差分约束 + Bellman-Ford 判负环,对应题目所在的「图论」章节,负环视角更通用;
- Python 版:带权并查集。Python 里
的松弛(约 次) 常数偏大,换用并查集后每组只要 次带路径压缩的查找,稳过 1 s 限时。 两者是同阶模型的两个实现,算法没有降级。
易错与边界。
: 就是"单月收入 = w",代码里 与 仍是两个不同结点,不需要特判。 可以是 或负数:两种做法都只看数值,不依赖 。 - 同一个区间给出两个不同的
:必然冲突,输出 false。 题面没给范围,前缀和可以累到 ,C++ 里一律用 long long防溢出。- 没有任何信息牵涉到的月份不影响判定:它的
可以自由取值,虚源边把它纳入可达范围即可。
代码
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:56
# update_at: 2026-10-07 18:56
import sys
from collections.abc import Iterator
# 结点 0..n 表示前缀和 s[0..n](s[0] = 0)。并查集里用「势」记录差:
# pot[i] = s[i] - s[parent[i]],含义只在这里解释一次,合并时靠它把两棵树的
# 差值对齐,从而维护每条信息 s[y] - s[x-1] = w。
def find(x: int, parent: list[int], pot: list[int]) -> int:
"""返回 x 所在集合的根,并沿路压缩,使 pot[x] = s[x] - s[根]。"""
root = x
total = 0 # 沿路径累计的势,就是 s[x] - s[根]
while parent[root] != root:
total += pot[root]
root = parent[root]
cur, acc = x, total
while parent[cur] != cur: # 第二趟:沿途结点直接挂到根上,势一并压平
nxt, step = parent[cur], pot[cur]
parent[cur], pot[cur] = root, acc
acc -= step
cur = nxt
return root
def unite(a: int, b: int, w: int, parent: list[int], pot: list[int]) -> bool:
"""声明 s[b] - s[a] = w;返回 False 表示与已有信息矛盾。"""
ra, rb = find(a, parent, pot), find(b, parent, pot)
pa, pb = pot[a], pot[b] # 压缩之后 pot[x] = s[x] - s[根]
if ra == rb:
return pb - pa == w # 同一集合:已有的差必须正好是 w
parent[rb] = ra
pot[rb] = pa + w - pb # 对齐两棵树的势,让 s[b] - s[a] = w 成立
return True
def judge_group(n: int, m: int, data: Iterator[int]) -> bool:
"""读入并合并这一组的 m 条信息,返回账本是否可能为真。"""
parent = list(range(n + 1)) # 结点 0..n 即前缀和 s[0..n]
pot = [0] * (n + 1) # 初始各自成根,势全 0
consistent = True
for _ in range(m):
x, y, w = next(data), next(data), next(data)
# 第 x..y 月的总收入 = s[y] - s[x-1],逐条并入并查集
consistent = consistent and unite(x - 1, y, w, parent, pot)
return consistent
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
out: list[str] = []
T = next(data)
for _ in range(T):
n, m = next(data), next(data)
out.append("true" if judge_group(n, m, data) else "false")
print("\n".join(out))
if __name__ == "__main__":
solve()C++ 版(同一模型,差分约束 + Bellman-Ford 判负环):
/**
* 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:56
* update_at: 2026-10-07 18:56
*/
// 一本通 1725 账本核算:前缀和 + 差分约束,Bellman-Ford 判负环。
// 记 s[i] = A[1] + ... + A[i],则「第 x..y 月总收入 = w」就是 s[y] - s[x-1] = w。
// 只要这组等式有整数解,就能反推出一个合法账本;有负环说明等式组自相矛盾。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXV = 105; // 结点 0..n 表示前缀和 s[0..n],另有虚源,n < 100
const int MAXE = 512; // 每条信息拆成 2 条有向边,再加 n+1 条虚源边,总数 < 300
struct Edge {
int to; // 终点
ll w; // 边权
int nxt; // 链式前向星里的下一条出边编号
};
int head[MAXV]; // head[u] = u 的第一条出边编号,0 表示没有出边
Edge edge[MAXE]; // 边表,1 号边开始使用
int edge_cnt; // 已加入的边数
ll dist[MAXV]; // dist[v] = 当前求得的 s[v] 上界(虚源到 v 的最短路)
// 加入一条 u -> v、权为 w 的有向边
void add_edge(int u, int v, ll w) {
edge_cnt++;
edge[edge_cnt].to = v;
edge[edge_cnt].w = w;
edge[edge_cnt].nxt = head[u];
head[u] = edge_cnt;
}
void solve() {
int T;
scanf("%d", &T);
while (T-- > 0) {
int n, m;
scanf("%d %d", &n, &m);
int src = n + 1; // 虚源:向所有前缀和结点连 0 权边,保证全图可达
int V = n + 2; // 结点 0..n 加上虚源,共 V 个
edge_cnt = 0;
for (int i = 0; i < V; i++) head[i] = 0;
for (int i = 0; i < m; i++) {
int x, y;
ll w;
scanf("%d %d %lld", &x, &y, &w);
// s[y] - s[x-1] = w 拆成两条三角不等式:
// s[y] <= s[x-1] + w 与 s[x-1] <= s[y] - w
add_edge(x - 1, y, w);
add_edge(y, x - 1, -w);
}
for (int i = 0; i <= n; i++) add_edge(src, i, 0);
// 全 0 初值等价于「虚源的 0 权入边已经松弛过一轮」
for (int i = 0; i < V; i++) dist[i] = 0;
bool has_negative_cycle = false;
for (int it = 0; it < V; it++) {
bool changed = false;
for (int u = 0; u < V; u++) {
for (int e = head[u]; e; e = edge[e].nxt) {
int v = edge[e].to;
if (dist[u] + edge[e].w < dist[v]) {
dist[v] = dist[u] + edge[e].w;
changed = true;
}
}
}
if (!changed) break; // 已经收敛,说明无负环
if (it == V - 1) has_negative_cycle = true; // 第 V 轮仍能松弛 => 有负环
}
printf(has_negative_cycle ? "false\n" : "true\n");
}
}
int main() {
solve();
return 0;
}复杂度
- 时间:C++ 版每组
, 组总计 ;Python 版每组 ,近似线性。 - 空间:C++ 版
(边表 条、 dist[]约个 long long); Python 版(两个长度 的列表)。
总结
本题的题眼只有一句:把区间和换成前缀和之差。换完之后,
“若干区间和"变成"若干变量对的差”,于是问题就落到两个经典模型上——
差分约束(无负环
需要说明的两点材料情况:本题素材源自带 data.py 生成脚本,说明随仓测试数据是自行构造的
(生成器内置带权并查集判决器保证 true / false 标签真实),题面亦为按公开题面重建,
出题意图与官方原题可能存在偏差;std.cpp 为参考网络公开题解
(同型题如 HNOI2005《狡猾的商人》)后独立实现的 Bellman-Ford 版本,
已用随仓全部 10 个测试点实跑核对,与 .out 完全一致。