账本核算

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

把月度收入换成前缀和 s[i],每条记录即 s[y]-s[x-1]=w;等式组化成差分约束判负环(带权并查集同样可判),矛盾则输出 false。

OJ: roj

题目 ID: 1725

难度:提高+/省选-

标签:图论差分约束并查集负环python

创建: 2026-10-07 18:56

更新: 2026-10-07 18:56

形式化题目

有一个长度为 nn 的整数序列 A1,A2,…,AnA_1, A_2, \dots, A_n(可正可负,表示每月的盈亏), 以及 mm 条形如

Ax+Ax+1+⋯+Ay=wA_x + A_{x+1} + \dots + A_y = w

的信息,其中 1⩽x⩽y⩽n1 \leqslant x \leqslant y \leqslant n。问:是否存在满足全部 mm 条信息的整数序列 AA。 每组数据输出 true(存在)或 false(不存在)。

数据范围:T<100T < 100,n,m<100n, m < 100,1⩽x⩽y⩽n1 \leqslant x \leqslant y \leqslant n;题面未给 ww 的范围。

关键的量只有「区间和」,而区间和可以互相加减。以样例的两组数据为例:

组 信息 从信息推出的关系 结论
1 s2−s0=10s_2 - s_0 = 10,s3−s0=−5s_3 - s_0 = -5,s3−s2=−15s_3 - s_2 = -15 前两条给出 s2=10,s3=−5s_2 = 10, s_3 = -5,第三条 s3−s2=−15s_3 - s_2 = -15 正好吻合 true
2 s5−s0=100s_5 - s_0 = 100,s5−s2=50s_5 - s_2 = 50,s2−s0=51s_2 - s_0 = 51 两条路算出 s5−s0s_5 - s_0 分别是 100100 与 50+51=10150 + 51 = 101 false

(表中 si=A1+⋯+Ais_i = A_1 + \dots + A_i。)第二组的矛盾形态正是本题的核心: 同一个差值被两条不同路径给出了不同的值,账本就不可能存在。

正解

思路

第一步:把区间和换成前缀和。

设 s0=0s_0 = 0,si=A1+A2+⋯+Ais_i = A_1 + A_2 + \dots + A_i。于是

Ax+⋯+Ay=sy−sx−1,Ai=si−si−1.A_x + \dots + A_y = s_y - s_{x-1}, \qquad A_i = s_i - s_{i-1}.

一条信息 Ax+⋯+Ay=wA_x + \dots + A_y = w 就变成只涉及两个变量的等式

sy−sx−1=w.(1)s_y - s_{x-1} = w. \tag{1}

这一步为什么有用?直接对 AA 下手时,每条信息牵动 y−x+1y - x + 1 个变量,相邻信息之间互相纠缠, 没法单独判断;换到前缀和后,每条信息只锁住两个变量之间的差, 而"差"是可以沿着信息链传递、相加、比较的。

还要确认:ss 上的解能不能还原成 AA?能。任意一组满足 s0=0s_0 = 0 的 s0,s1,…,sns_0, s_1, \dots, s_n 唯一确定 Ai=si−si−1A_i = s_i - s_{i-1},且这组 AA 恰好满足所有 (1) 式。所以

账本存在  ⟺  等式组 {sy−sx−1=w} 有解.\text{账本存在} \iff \text{等式组 } \{s_y - s_{x-1} = w\} \text{ 有解}.

第二步:等式组转成差分约束图。

把每个等式 (1) 拆成两条不等式:

sy⩽sx−1+w,sx−1⩽sy−w.(2)s_y \leqslant s_{x-1} + w, \qquad s_{x-1} \leqslant s_y - w. \tag{2}

这两条不等式同时成立就等价于等式成立。于是把 s0,s1,…,sns_0, s_1, \dots, s_n 看成 n+1n+1 个结点, 每条 (2) 式对应一条带权有向边(“sv⩽su+cs_v \leqslant s_u + c” 记作 u→vu \to v 权 cc):

不等式 有向边
sy⩽sx−1+ws_y \leqslant s_{x-1} + w (x−1)→y(x-1) \to y,权 ww
sx−1⩽sy−ws_{x-1} \leqslant s_y - w y→(x−1)y \to (x-1),权 −w-w

第三步:无负环   ⟺  \iff 有解。

差分约束系统的标准结论:不等式组 sv⩽su+cs_v \leqslant s_u + c 有解,当且仅当这张图里没有负环。

  • 若有负环 v1→v2→⋯→vk→v1v_1 \to v_2 \to \dots \to v_k \to v_1,把环上不等式逐条相加得到 sv1⩽sv1+(环权和)<sv1s_{v_1} \leqslant s_{v_1} + (\text{环权和}) < s_{v_1},矛盾,无解。
  • 若无负环,就取 svs_v 为源点到 vv 的最短路长度,则对每条边 u→vu \to v 都有 sv⩽su+cs_v \leqslant s_u + c(最短路的三角不等式),是一组解。

第四步:为什么整数解等价于实数解。

上面的构造用最短路给出解,而本题所有边权 w,−ww, -w 都是整数, 最短路长度必为整数,所以只要实数有解就一定有整数解, 不必额外担心"账本记录的是整数金额"。这一点值得单独写出来, 因为题面只说 AiA_i 是整数,没有说允许分数。

第五步:怎么判负环。

结点数 V=n+2⩽101V = n + 2 \leqslant 101,边数 E=2m+(n+1)⩽300E = 2m + (n+1) \leqslant 300, 规模极小,用最朴素的 Bellman-Ford 即可:以虚源(向所有结点连 00 权边, 保证全图可达)为起点松弛,若第 VV 轮仍能松弛,说明存在负环。之所以不用 SPFA:

  1. 规模下 O(VE)⩽3×104O(VE) \leqslant 3 \times 10^4,T⩽99T \leqslant 99 组总计 <3×106< 3 \times 10^6,远够用;
  2. Bellman-Ford 是确定性的,不会被 SPFA 的随机化数据卡掉。

实现上有个小技巧:直接把 dist[] 全部初始化为 00,等价于"虚源的 00 权边已经松弛过一轮", 连建虚源边都可以省掉(写出来更清楚,两种写法都行)。

等价视角:带权并查集。

等式组还有另一条更快的路。把 (1) 式看成"x−1x-1 与 yy 在同一集合内,且 sy−sx−1=ws_y - s_{x-1} = w",用带权并查集维护每个结点与所在集合根的差 pot[i]=si−sroot(i)\mathrm{pot}[i] = s_i - s_{\mathrm{root}(i)}:

  • 若 x−1x-1 与 yy 已在同一集合,读出两者与根的差相减, 得到已有的 sy−sx−1s_y - s_{x-1},与 ww 不符就矛盾;
  • 否则合并两棵树,把被挂上去的根的势设成 pot[a]+w−pot[b]\mathrm{pot}[a] + w - \mathrm{pot}[b],使等式成立。

它和负环判定是同一件事:合并冲突   ⟺  \iff 出现负环。 每条信息都是"同集合内差必须等于 ww",合并成功后集合内所有差都一致, 所以不冲突就说明等式组无矛盾、有解。复杂度 O((n+m) α(n))O((n+m)\,\alpha(n)), 常数比 Bellman-Ford 小得多。

本文给出两份代码,正是同一模型的两条落地路线:

  • C++ 版:差分约束 + Bellman-Ford 判负环,对应题目所在的「图论」章节,负环视角更通用;
  • Python 版:带权并查集。Python 里 T×V×ET \times V \times E 的松弛(约 3×1063 \times 10^6 次) 常数偏大,换用并查集后每组只要 O(m)O(m) 次带路径压缩的查找,稳过 1 s 限时。 两者是同阶模型的两个实现,算法没有降级。

易错与边界。

  • x=yx = y:sx−sx−1=ws_x - s_{x-1} = w 就是"单月收入 = w",代码里 x−1x-1 与 yy 仍是两个不同结点,不需要特判。
  • ww 可以是 00 或负数:两种做法都只看数值,不依赖 w>0w > 0。
  • 同一个区间给出两个不同的 ww:必然冲突,输出 false。
  • ww 题面没给范围,前缀和可以累到 n⋅∣w∣n \cdot |w|,C++ 里一律用 long long 防溢出。
  • 没有任何信息牵涉到的月份不影响判定:它的 sis_i 可以自由取值,虚源边把它纳入可达范围即可。

代码

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: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 判负环):

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: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++ 版每组 O(VE)=O((n+m) m)⩽3×104O(V E) = O\big((n+m)\,m\big) \leqslant 3 \times 10^4, T<100T < 100 组总计 <3×106< 3 \times 10^6;Python 版每组 O((n+m) α(n))O\big((n+m)\,\alpha(n)\big),近似线性。
  • 空间:C++ 版 O(n+m)O(n+m)(边表 <300< 300 条、dist[] 约 101101 个 long long); Python 版 O(n)O(n)(两个长度 n+1n+1 的列表)。

总结

本题的题眼只有一句:把区间和换成前缀和之差。换完之后, “若干区间和"变成"若干变量对的差”,于是问题就落到两个经典模型上—— 差分约束(无负环   ⟺  \iff 有解)和带权并查集(合并不冲突   ⟺  \iff 有解)。 两者的正确性依赖同一条事实:等式组的所有推论都表现为"两个变量的差", 只要沿着信息链传递差值时不出现矛盾,就能任选一个自由变量、把其余变量全部定下来, 再还原出账本。

需要说明的两点材料情况:本题素材源自带 data.py 生成脚本,说明随仓测试数据是自行构造的 (生成器内置带权并查集判决器保证 true / false 标签真实),题面亦为按公开题面重建, 出题意图与官方原题可能存在偏差;std.cpp 为参考网络公开题解 (同型题如 HNOI2005《狡猾的商人》)后独立实现的 Bellman-Ford 版本, 已用随仓全部 10 个测试点实跑核对,与 .out 完全一致。