把行、列的整体加减记成整数 r、c,限制化为 r_x+c_y=c 的差值等式,用带权并查集维护点值差并在同集合时判矛盾。
OJ: roj
题目 ID: 1726
难度:普及+/提高-
标签:并查集图论python
创建: 2026-10-07 18:53
更新: 2026-10-07 18:53
形式化题目
有一个
- 选一行,该行每个格子的权值同时
或 ; - 选一列,该列每个格子的权值同时
或 。
给出 Yes,否则输出 No。
多组数据,第一行给出组数
把操作过程的信息压缩掉以后,题目等价于:求一组整数
正解
思路
为什么可以只看净次数。 对第
朴素做法卡在哪。 直接搜索
关键观察:约束全是"等式"。 每条限制只涉及两个变量,而等式可以改写成差值形式:
把第
即"两个点之间的差值被定死了"。这类约束有一个漂亮性质:差值沿路径可加。
已知
矛盾长什么样。 只有一种出错可能:绕一圈回来发现某点和"自己"的值差不是
用带权并查集维护。 上述"路径可加 + 同分量差值唯一"正好是带权并查集能表达的形态。
为每个点
| 名称 | 含义 |
|---|---|
fa[i] |
并查集的父节点,fa[i] == i 表示 |
val[i] |
对每条限制
- 同根:两点的值差已被完全确定,就是
, 它必须等于 ,否则这条限制与已有信息冲突,答案 No。 - 不同根:两点之间原本没有任何约束,这条限制不可能矛盾,直接合并两棵树。
设两根为
root_x、root_col,把root_col挂到root_x下,偏移量由等式反解:
推导只需两步:由
为什么整数解一定存在。 上面所有运算都只是整数加减(
用样例第 2 组数据看看矛盾是如何暴露的。限制为 No。
实现上的两个易错点。 一是 val 是"对父节点"的差值,路径压缩必须先把整条路径的
偏移量求出来再自近根端往叶端改写(先累加出 值(x) - 值(root),再逐点把 val 改成对根的差值),
否则 val 里混着对不同祖先的差值,链长 val[root_col]),而不是列点的偏移量。
代码
#!/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:53
# update_at: 2026-10-07 18:53
import sys
from collections.abc import Iterator
def find_root(x: int, fa: list[int], val: list[int]) -> int:
"""返回 x 所在集合的根,并把路径上每点的 val 压成「值(点) − 值(根)」。
val[i] 的含义是「值(i) − 值(fa[i])」这种相对差值,所以先沿原路求出
total = 值(x) − 值(root),再自 x 向根逐点把 val 改写成「对根的差值」,
顺便把 fa 直接指向根(路径压缩)。
"""
root = x
while fa[root] != root:
root = fa[root]
total = 0 # 值(x) − 值(root)
node = x
while node != root:
total += val[node]
node = fa[node]
pre = 0 # 值(x) − 值(node)
node = x
while node != root:
nxt = fa[node]
diff = total - pre # 值(node) − 值(root)
pre += val[node] # 下一轮要用的「值(x) − 值(nxt)」,必须先用旧 val
val[node] = diff
fa[node] = root
node = nxt
return root
def add_constraints(n: int, k: int, data: Iterator[int], fa: list[int], val: list[int]) -> bool:
"""顺序读入 k 条限制,边判定边合并,返回所有限制能否同时满足。
限制 (x, y, c) 统一成差值等式「值(x) − 值(n+y) = c」:同集合就核对值差,
不同集合就按这个等式反解出根的偏移量后合并。
"""
ok = True # 是否所有限制能同时满足
for _ in range(k):
x, y, c = next(data), next(data), next(data)
col = n + y
root_x, root_col = find_root(x, fa, val), find_root(col, fa, val)
if root_x == root_col:
# 同一集合:值差已被推出,必须恰好等于 c,否则出现环上的矛盾
known = val[x] - val[col]
ok = ok and known == c
else:
# 不同集合:把 col 的根挂到 x 的根下,偏移量由等式反解
fa[root_col] = root_x
val[root_col] = val[x] - val[col] - c
return ok
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
out: list[str] = []
T = next(data)
for _ in range(T):
n, m, k = next(data), next(data), next(data)
# 行点 1..n 与列点 n+1..n+m 共处一张并查集;列点的「值」取 −(该列净操作数),
# 这样限制 (x, y, c) 就统一成差值等式「值(x) − 值(n+y) = c」。
fa = list(range(n + m + 1))
val = [0] * (n + m + 1) # val[i] = 值(i) − 值(fa[i])
out.append("Yes" if add_constraints(n, k, data, fa, val) else "No")
print("\n".join(out))
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:53
* update_at: 2026-10-07 18:53
*
* 一本通 1726《矩阵》(同 BZOJ 4500)
*
* 建模:矩阵初值全 0,对第 i 行整体加减的总净次数记 r_i,对第 j 列记 c_j
* (加减可互相抵消,所以 r_i、c_j 是任意整数,操作序列存在 <=> 存在整数 r、c)。
* 于是限制 (x, y, c) 就是 r_x + c_y = c,全是"等式约束",可行性 = 方程组是否有整数解。
*
* 做法(带权并查集):把每一行、每一列都看成一个点,行点编号 1..n,列点编号 n+1..n+m,
* 并令列点 n+y 的"值"取 -(第 y 列的净操作数),则每条限制化为**差值等式**
* 值(x) - 值(n+y) = c,
* 这正是带权并查集能维护的形式:同集合内核对值差,不同集合则按值差合并。
*
* 正确性:约束全为整系数等式,解在有理数域存在时并查集给出的偏移量全为整数,
* 故整数可解性与实数可解性一致;矛盾判据"环上值差之和 != 0"等价于无解。
*
* 数据范围(content.md):T <= 5;1 <= n,m,k <= 1000 且 k <= n*m;c 的区间题面未给,用 ll 承载。
* 复杂度:每组 O((n+m) + k*alpha),T <= 5、n+m <= 2000、k <= 1000,远低于 2000 ms。
*/
#include <cstdio>
typedef long long ll;
const int MAXV = 2005; // 行点 1..n 与列点 n+1..n+m,n+m <= 2000
ll fa[MAXV]; // fa[i] 是并查集父节点,fa[i] == i 表示 i 是根
ll val[MAXV]; // val[i] = 值(i) - 值(fa[i]),即 i 到父节点的值差
// 找 x 的根,同时把路径上每点的 val 压成"值(点) - 值(根)"
ll find_root(ll x) {
ll root = x;
while (fa[root] != root) root = fa[root];
// 第一遍:求出 total = 值(x) - 值(root)
ll total = 0;
ll node;
for (node = x; node != root; node = fa[node]) total += val[node];
// 第二遍:自 x 向根压路径,pre = 值(x) - 值(node)
ll pre = 0;
node = x;
while (node != root) {
ll nxt = fa[node];
ll old = val[node];
val[node] = total - pre; // 值(node) - 值(root)
fa[node] = root; // 路径压缩
pre += old;
node = nxt;
}
return root;
}
int main() {
ll T;
scanf("%lld", &T);
while (T--) {
ll n, m, k;
scanf("%lld %lld %lld", &n, &m, &k);
for (ll i = 1; i <= n + m; i++) {
fa[i] = i;
val[i] = 0;
}
bool ok = true; // 是否存在满足全部限制的整数操作序列
for (ll i = 1; i <= k; i++) {
ll x, y, c;
scanf("%lld %lld %lld", &x, &y, &c);
ll col = n + y; // 第 y 列对应的列点编号
ll root_x = find_root(x);
ll root_col = find_root(col);
if (root_x == root_col) {
// 同一集合:值(x) - 值(col) 已被推出,必须恰好等于 c
if (val[x] - val[col] != c) ok = false;
} else {
// 不同集合:把 col 的根挂到 x 的根下,新根到新父的值差由等式反解
fa[root_col] = root_x;
val[root_col] = val[x] - val[col] - c;
}
}
printf("%s\n", ok ? "Yes" : "No");
}
return 0;
}复杂度
每组数据的时间为
总结
本题是"等式型约束系统 = 带权并查集"的模板题,核心是三步转换:
- 消掉操作序列:行、列的加减互相独立且可抵消,只留下净次数
, 存在性等价于方程组 有整数解; - 把加法等式改成差值等式:列点点值取
,约束统一成 , 差值沿路径可加; - 带权并查集承载差值:同集合核对值差是否等于
,不同集合按 val[root_col] = val[x] - val[col] - c合并。
变体说明:同一模型也可以用"每个格子一条边、跑 SPFA 判负环"的差分约束写法实现
(
说明:本目录
problem.md取材自仓库素材源(content.md),其同题在 BZOJ 为 4500《矩阵》; 数据由素材源自带的生成脚本data.py分层自造(本目录不包含测试数据与生成脚本)。 题面未给的取值范围,实现中一律用 64 位整数承载 与路径偏移。