题目链接：「联合省选 2021 A」矩阵游戏 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 「联合省选 2021 A」矩阵游戏 题解 题目描述 给定一个 (n−1)×(m−1)(n-1) \times (m-1)(n−1)×(m−1) 的矩阵 bbb，其中 bi,j=ai,j+ai,j+1+ai+1,j+ai+1,j+1b_{i,j} = a_{i,j} + a_{i,j+1} + a_{i+1,j} + a_{i+1,j+1} bi,j =ai,j +ai,j+1 +ai+1,j +ai+1,j+1 要求还原一个 n×mn \times mn×m 的非负整数矩阵 aaa，且每个元素不超过 10610^6106。若不存在，输出 NO，否则输出 YES 并给出任意一个合法矩阵。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 算法分析 1. 构造初始解 先忽略大小限制，任意求出一组满足方程的解。令 a1,1=0a_{1,1}=0a1,1 =0，并设第一行和第一列均为 000，然后利用递推式： ai+1,j+1=bi,j−ai,j−ai,j+1−ai+1,ja_{i+1,j+1} = b_{i,j} - a_{i,j} - a_{i,j+1} - a_{i+1,j} ai+1,j+1 =bi,j −ai,j −ai,j+1 −ai+1,j 可以依次求出所有 ai,ja_{i,j}ai,j 。记该初始解为 fi,jf_{i,j}fi,j （可能含有负数或超过 10610^6106）。 2. 调整变量保持 BBB 不变 对于任意一组 xix_ixi （1≤i≤n1 \le i \le n1≤i≤n）和 yjy_jyj （1≤j≤m1 \le j \le m1≤j≤m），定义 ai,j=fi,j+(−1)i+j(xi+yj)a_{i,j} = f_{i,j} + (-1)^{i+j} (x_i + y_j) ai,j =fi,j +(−1)i+j(xi +yj ) 则新的 aaa 仍然满足所有 bbb 方程，因为 (−1)i+j(-1)^{i+j}(−1)i+j 在 2×22\times22×2 块中交替正负，求和后抵消。 因此问题转化为：寻找整数（或实数）xi,yjx_i, y_jxi ,yj ，使得对所有格子都有 0≤fi,j+(−1)i+j(xi+yj)≤1060 \le f_{i,j} + (-1)^{i+j} (x_i + y_j) \le 10^6 0≤fi,j +(−1)i+j(xi +yj )≤106 3. 转化为差分约束 令 p=(−1)i+jp = (-1)^{i+j}p=(−1)i+j，则约束等价于： * 若 p=1p = 1p=1： −fi,j≤xi+yj≤106−fi,j-f_{i,j} \le x_i + y_j \le 10^6 - f_{i,j} −fi,j ≤xi +yj ≤106−fi,j * 若 p=−1p = -1p=−1： fi,j−106≤xi+yj≤fi,jf_{i,j} - 10^6 \le x_i + y_j \le f_{i,j} fi,j −106≤xi +yj ≤fi,j 设变量 vi=xiv_i = x_ivi =xi （1≤i≤n1 \le i \le n1≤i≤n），vn+j=−yjv_{n+j} = -y_jvn+j =−yj （1≤j≤m1 \le j \le m1≤j≤m）。则 xi+yj=vi−vn+jx_i + y_j = v_i - v_{n+j}xi +yj =vi −vn+j 。 于是每个约束形如 L≤vi−vn+j≤UL \le v_i - v_{n+j} \le U L≤vi −vn+j ≤U 即 vi−vn+j≤U和vn+j−vi≤−Lv_i - v_{n+j} \le U \quad \text{和} \quad v_{n+j} - v_i \le -L vi −vn+j ≤U和vn+j −vi ≤−L 这是典型的差分约束系统：对于不等式 vu−vv≤wv_u - v_v \le wvu −vv ≤w，连边 v→uv \to uv→u，权值为 www。若图中存在负环，则无解。 4. 求解与构造 * 添加超级源点 000，向所有变量连权值为 000 的边，以消除孤立点。 * 使用 SPFA 求单源最短路，同时检测负环。 * 若无负环，则得到一组可行解 xi=dist[i]x_i = \mathrm{dist}[i]xi =dist[i]，yj=−dist[n+j]y_j = -\mathrm{dist}[n+j]yj =−dist[n+j]。 * 最终矩阵为： ai,j=fi,j+(−1)i+j(xi+yj)a_{i,j} = f_{i,j} + (-1)^{i+j} (x_i + y_j) ai,j =fi,j +(−1)i+j(xi +yj ) 输出即可。 5. 复杂度 每个格子产生两条约束边，总边数 O(nm)O(nm)O(nm)，节点数 O(n+m)O(n+m)O(n+m)，SPFA 在随机数据下表现良好，可通过本题。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ CODE: 注意事项： * 所有变量使用 long long 防止中间计算溢出。 * 差分约束中的边权可能为负，SPFASPFASPFA 需正确检测负环。 * 初始解 f 的构造无特殊限制，但需保证所有格子被计算。 * 最终输出的每个元素应在 [0,1e6][0, 1e6][0,1e6] 内，若因浮点误差导致微小偏差，可四舍五入，但本题均为整数，不会有误差。 该算法时间复杂度为 O(T∗(n+m)∗E)O(T * (n+m) * E)O(T∗(n+m)∗E)，其中 E=2nm+n+mE = 2nm + n + mE=2nm+n+m，在 n,m<=300n,m <= 300n,m<=300 时完全可行。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 这道题样例错误，应输出以下： 两种答案逻辑上两者都正确。