矩阵

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

把行、列的整体加减记成整数 r、c,限制化为 r_x+c_y=c 的差值等式,用带权并查集维护点值差并在同集合时判矛盾。

OJ: roj

题目 ID: 1726

难度:普及+/提高-

标签:并查集图论python

创建: 2026-10-07 18:53

更新: 2026-10-07 18:53

形式化题目

有一个 n×mn \times m 的矩阵,初始每个格子的权值都是 00。可以重复执行两种操作:

  1. 选一行,该行每个格子的权值同时 +1+1 或 −1-1;
  2. 选一列,该列每个格子的权值同时 +1+1 或 −1-1。

给出 kk 个限制,每个限制是三元组 (x,y,c)(x, y, c),要求操作结束后格子 (x,y)(x, y) 的权值恰好为 cc。 问是否存在这样的操作序列:存在输出 Yes,否则输出 No。

多组数据,第一行给出组数 T⩽5T \leqslant 5;每组先给 n,m,kn, m, k(1⩽n,m,k⩽10001 \leqslant n, m, k \leqslant 1000,且 k⩽n×mk \leqslant n \times m), 随后 kk 行限制。

把操作过程的信息压缩掉以后,题目等价于:求一组整数 (r1,…,rn,  c1,…,cm)(r_1, \dots, r_n,\; c_1, \dots, c_m),使得对每条限制 (x,y,c)(x, y, c) 都有 rx+cy=cr_x + c_y = c。

正解

思路

为什么可以只看净次数。 对第 ii 行一共加 aa 次、减 bb 次,它的净效果是整行加 a−ba-b; 对第 jj 列同理,净效果是整列加 cjc_j。操作之间的先后顺序对最终矩阵毫无影响, 格子 (x,y)(x, y) 的权值只等于 rx+cyr_x + c_y。反过来任意一组整数 r,cr, c 都能实现: 第 ii 行做 ∣ri∣|r_i| 次加减(ri>0r_i > 0 就加、ri<0r_i < 0 就减),列同理。 于是操作序列存在   ⟺  \iff 方程组 rx+cy=cr_x + c_y = c 有整数解。

朴素做法卡在哪。 直接搜索 rr 的取值是无穷的(可正可负、可任意大),枚举范围说不出来; 而 k⩽n×mk \leqslant n \times m,逐格模拟矩阵也无法判定解是否存在。

关键观察:约束全是"等式"。 每条限制只涉及两个变量,而等式可以改写成差值形式: 把第 yy 列的净操作数取负,令列点(编号 n+yn+y)的"值"为 −cy-c_y,限制就变成

值(x)−值(n+y)=c,\text{值}(x) - \text{值}(n + y) = c,

即"两个点之间的差值被定死了"。这类约束有一个漂亮性质:差值沿路径可加。 已知 值(a)−值(b)=w1\text{值}(a) - \text{值}(b) = w_1 与 值(b)−值(d)=w2\text{值}(b) - \text{值}(d) = w_2, 就有 值(a)−值(d)=w1+w2\text{值}(a) - \text{值}(d) = w_1 + w_2,不必再检查什么。 把行点、列点都当成图的顶点,每条限制当成一条带权边,则同一连通分量内的所有点值差 都被唯一确定;分量之间互不干扰,可以各自独立赋值。

矛盾长什么样。 只有一种出错可能:绕一圈回来发现某点和"自己"的值差不是 00。 也就是存在闭合走法,把沿途边的权值按行走方向带符号相加后得到非零值—— 这正是方程组无解(矛盾)的充要条件。

用带权并查集维护。 上述"路径可加 + 同分量差值唯一"正好是带权并查集能表达的形态。 为每个点 ii 维护两个量:

名称 含义
fa[i] 并查集的父节点,fa[i] == i 表示 ii 是根
val[i] 值(i)−值(fa[i])\text{值}(i) - \text{值}(\texttt{fa}[i]),即 ii 到父节点的值差

对每条限制 (x,y,c)(x, y, c),令 col=n+y\text{col} = n + y:

  1. 同根:两点的值差已被完全确定,就是 val[x]−val[col]\texttt{val}[x] - \texttt{val}[\text{col}], 它必须等于 cc,否则这条限制与已有信息冲突,答案 No。
  2. 不同根:两点之间原本没有任何约束,这条限制不可能矛盾,直接合并两棵树。 设两根为 root_x、root_col,把 root_col 挂到 root_x 下,偏移量由等式反解:
val[root_col]=val[x]−val[col]−c.\texttt{val}[\text{root\_col}] = \texttt{val}[x] - \texttt{val}[\text{col}] - c .

推导只需两步:由 值(x)−值(col)=c\text{值}(x) - \text{值}(\text{col}) = c 代入 值(x)=值(root_x)+val[x]\text{值}(x) = \text{值}(\text{root\_x}) + \texttt{val}[x]、 值(col)=值(root_col)+val[col]\text{值}(\text{col}) = \text{值}(\text{root\_col}) + \texttt{val}[\text{col}], 移项即得 值(root_col)−值(root_x)=val[x]−val[col]−c\text{值}(\text{root\_col}) - \text{值}(\text{root\_x}) = \texttt{val}[x] - \texttt{val}[\text{col}] - c。

为什么整数解一定存在。 上面所有运算都只是整数加减(cc 是整数,路径偏移是整数之和), 根的值随便取一个整数即可,解出的 r,cr, c 自然全是整数。 所以这里"实数可解"与"整数可解"没有区别,不需要额外讨论。

用样例第 2 组数据看看矛盾是如何暴露的。限制为 (1,1,0),(1,2,0),(2,1,2),(2,2,1)(1,1,0), (1,2,0), (2,1,2), (2,2,1), 不妨取 值(1)=0\text{值}(1) = 0,则 (1,1,0)(1,1,0) 给出 值(3)=0\text{值}(3) = 0,(1,2,0)(1,2,0) 给出 值(4)=0\text{值}(4) = 0; 再由 (2,1,2)(2,1,2) 得 值(2)=值(3)+2=2\text{值}(2) = \text{值}(3) + 2 = 2。 最后的 (2,2,1)(2,2,1) 与前面已连通,要求 值(2)−值(4)=1\text{值}(2) - \text{值}(4) = 1, 但已推出 2−0=2≠12 - 0 = 2 \neq 1,故输出 No。

实现上的两个易错点。 一是 val 是"对父节点"的差值,路径压缩必须先把整条路径的 偏移量求出来再自近根端往叶端改写(先累加出 值(x) - 值(root),再逐点把 val 改成对根的差值), 否则 val 里混着对不同祖先的差值,链长 ⩾3\geqslant 3 就会错; 二是合并时挂的是根的偏移量(val[root_col]),而不是列点的偏移量。

代码

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: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()
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: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;
}

复杂度

每组数据的时间为 O((n+m)+k α(n+m))O((n + m) + k\,\alpha(n + m)):初始化 n+mn+m 个点,每条限制一次查根加可能的合并; 组数 T⩽5T \leqslant 5,实际总量 ⩽5×(2000+1000)\leqslant 5 \times (2000 + 1000) 次操作。空间 O(n+m)O(n + m)。 在 2000 ms / 256 MB 下余量极大,CPython 实测本目录 10 个测点(含 T=5T=5、n=m=1000n=m=1000、k=1000k=1000 的顶格数据) 全部在数十毫秒量级完成。

总结

本题是"等式型约束系统 = 带权并查集"的模板题,核心是三步转换:

  1. 消掉操作序列:行、列的加减互相独立且可抵消,只留下净次数 ri,cjr_i, c_j, 存在性等价于方程组 rx+cy=cr_x + c_y = c 有整数解;
  2. 把加法等式改成差值等式:列点点值取 −cy-c_y,约束统一成 值(x)−值(n+y)=c\text{值}(x) - \text{值}(n+y) = c, 差值沿路径可加;
  3. 带权并查集承载差值:同集合核对值差是否等于 cc,不同集合按 val[root_col] = val[x] - val[col] - c 合并。

变体说明:同一模型也可以用"每个格子一条边、跑 SPFA 判负环"的差分约束写法实现 (rx−(−cy)⩽cr_x - (-c_y) \leqslant c 与 −cy−rx⩽−c-c_y - r_x \leqslant -c 两条边),复杂度为 O(VE)O(VE), 在本题规模下更慢也更绕;带权并查集是这组"全等式约束"的最省做法。

说明:本目录 problem.md 取材自仓库素材源(content.md),其同题在 BZOJ 为 4500《矩阵》; 数据由素材源自带的生成脚本 data.py 分层自造(本目录不包含测试数据与生成脚本)。 题面未给 cc 的取值范围,实现中一律用 64 位整数承载 cc 与路径偏移。