题意
给出 \(n \times m (n,m\leq 500)\) 的矩阵 \(A\)。
可以进行以下操作任意次:
- 选择一个 \(2 \times 2\) 的矩阵加一个任意的整数 \(c\)。
求最小的权值和 \(\sum_{i=1}^{n}\sum_{j=1}^{m}|A_{i,j}|\)
特征化
令 \(B\) 为操作完后的矩阵。
\(2 \times 2\) 的矩阵通常满足一些奇偶性,
考虑到答案求的是绝对值,对正负号没有影响。
将其结合就能得到关于行和列的特殊的恒等式:
对于任意行 \(i\):
\[\sum_{j=1}^{m}(-1)^{i+j}A_{i,j} = \sum_{j=1}^{m} (-1)^{i + j} B_{i,j} \]对于任意列 \(j\):
\[\sum_{i=1}^{n}(-1)^{i+j}A_{i,j} = \sum_{i=1}^{n} (-1)^{i + j} B_{i,j} \]也就是同一行同一列的加入的连续的两个数 \(x\) 互为相反数,相加相互抵消。
就能得到限制 \(B\) 矩阵的不变量。
- 换句话说,只要 \(B\) 满足上面的性质,那么 \(A\) 就一定能变成 \(B\)。
转化
现在问题变成了:
将全零矩阵 \(B\) 变成 满足每行每列的和与 \(A\) 相同的矩阵,满足 \(\sum_{i=1}^{n}\sum_{j=1}^{m}|B_{i,j}|\) 最小。
这同把 \(A\) 变为全零矩阵, 同时在 \(B\) 做相反操作是等价的。
令 \(x_i\) 为 \(A\) 矩阵第 \(i\) 行的和, \(y_j\) 为第 \(j\) 列的和,\(X = \sum_i |x_i|, Y = \sum_j |y_j|\)。
可以发现一次操作最多会使 \(X, Y\) 减去 \(|c|\)。
那么最小的和 \(\text{min} \geq \max\{X,Y\}\)
具体的步骤是:
- 如果 \(x_i > 0, y_j > 0\), 对 \(x_i, y_j\), 减去 \(\min{x_i, y_j}\)。
- 如果 \(x_i < 0, y_j < 0\), 对 \(x_i, y_j\), 减去 \(\max{x_i, y_j}\)。
- 如果 \(x_i > 0, x_j < 0\), 对 \(x_i, 1\), 减 \(\min\{x_i,-x_j\}\), 对 \(x_j, 1\) 减 \(-\min\{x_i,-x_j\}\)。
- 如果 \(y_i > 0, y_j < 0\), 对 \(1, y_i\), 减 \(\min\{y_i,-y_j\}\), 对 \(1, y_j\) 减 \(-\min\{y_i,-y_j\}\)。
对于第 1 和 2 点,因为总有 \(\sum_i x_i = \sum_j y_j\) 成立,总能找到同号的两个数做。
这样做到不能做后,肯定有 \(\forall i, x_i = 0 / \forall j,y_j = 0\)。
那么剩下两步就是对多余的进行处理,变成全零矩阵。
这样的构造是也是最优的构造。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 510;
int n, m;
ll X[MAXN], Y[MAXN], b[MAXN][MAXN];
void upd(int x, int y, ll c) {
X[x] -= c,
Y[y] -= c;
b[x][y] += (( (x + y) & 1 ) ? -1 : 1) * c;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++) {
ll x;
cin >> x;
if ((i + j) & 1) X[i] += -x, Y[j] += -x;
else X[i] += x, Y[j] += x;
}
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++) {
if (X[i] < 0 && Y[j] < 0) upd(i, j, max(X[i], Y[j]));
if (X[i] > 0 && Y[j] > 0) upd(i, j, min(X[i], Y[j]));
}
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
if (X[i] > 0 && X[j] < 0) {
ll c = min(X[i], - X[j]);
upd(i, 1, c);
upd(j, 1, -c);
}
for (int i = 1; i <= m; i ++)
for (int j = 1; j <= m; j ++)
if (Y[i] > 0 && Y[j] < 0) {
ll c = min(Y[i], -Y[j]);
upd(1, i, c);
upd(1, j, -c);
}
ll ans = 0;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
ans += abs(b[i][j]);
cout << ans << endl;
for (int i = 1; i <= n; i ++, cout << endl)
for (int j = 1; j <= m; j ++)
cout << b[i][j] << ' ';
return 0;
}