题意

ARC135D

给出 \(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\)：

对于任意列 \(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\}\)

具体的步骤是:

1. 如果 \(x_i > 0, y_j > 0\), 对 \(x_i, y_j\), 减去 \(\min{x_i, y_j}\)。
2. 如果 \(x_i < 0, y_j < 0\), 对 \(x_i, y_j\), 减去 \(\max{x_i, y_j}\)。
3. 如果 \(x_i > 0, x_j < 0\), 对 \(x_i, 1\), 减 \(\min\{x_i,-x_j\}\), 对 \(x_j, 1\) 减 \(-\min\{x_i,-x_j\}\)。
4. 如果 \(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;
}