构造 \(X_i=\sum_{j=1}^m (-1)^{i+j}A_{i,j}\)，\(Y_j=\sum_{i=1}^n (-1)^{i+j}A_{i,j}\)。
则一个矩阵 \(B\) 能被矩阵 \(A\) 变成当且仅当 \(\left\{X\right\},\left\{Y\right\}\) 均相等。
必要性：很显然，因为操作是不会导致 \(\left\{X\right\}\) 或 \(\left\{Y\right\}\) 改变的。
充分性：对于 \(i\in [1,n-1],j\in[1,m-1]\)，从上往下，从左到右依次调整，而每行的最右端与每列的最下端因为 \(\left\{X\right\},\left\{Y\right\}\) 均相等被唯一确定。
转换问题，变成给定 \(\left\{X\right\},\left\{Y\right\}\)，满足 \(\sum X_i=\sum Y_j\)，求一个 \(B\) 满足 \(X_i=\sum_{j=1}^m (-1)^{i+j}B_{i,j}\)，\(Y_j=\sum_{i=1}^n (-1)^{i+j}B_{i,j}\)，最小化 \(\sum \left|B_{i,j}\right|\)。
\(B\) 从全零矩阵开始操作，题目变成：
- 每次操作 \((i,j,k)\)，使得 \(X_i,Y_j\) 加上 \(k\)，代价为 \(\left|k\right|\)，需要让 \(\left\{X\right\},\left\{Y\right\}\) 都变成 \(0\)，最小化代价。
显然有个下界是 \(\sum \left|B_{i,j}\right|\ge \max(\sum\left|X_i\right|,\sum\left|Y_j\right|)\)，接下来构造一组能取到下界的解。
- 如果存在 \(X_i,Y_j\gt0\)，则操作 \((i,j,-1)\)。
- 如果存在 \(X_i,Y_j\lt0\)，则操作 \((i,j,1)\)。
- 如果存在 \(X_i\gt0,X_j\lt0\)，则操作 \((i,1,-1),(j,1,1)\)。
- 如果存在 \(Y_i\gt0,Y_j\lt0\)，则操作 \((1,i,-1),(1,j,1)\)。
容易发现由于 \(\sum X_i=\sum Y_j\)，则前两种操作完后，必有 \(\left\{X\right\}\) 或 \(\left\{Y\right\}\) 全为 \(0\)，后面两种操作就是对剩下非 \(0\) 的进行处理，每一步都是必要且不浪费的，因此这样能取到下界。
时间复杂度 \(\mathcal O(n^2)\)。
Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 505;
int n, m;
ll ans;
ll b[N][N];
ll X[N], Y[N];
void upd(int x, int y, ll c) {
X[x] -= c, Y[y] -= c;
b[x][y] += ((x + y) & 1) ? -c : c;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
ll k; scanf("%lld", &k);
if ((i + j) & 1) X[i] -= k, Y[j] -= k;
else X[i] += k, Y[j] += k;
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++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 <= m; ++j)
if (X[i] < 0 && Y[j] < 0)
upd(i, j, max(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 tmp = min(X[i], -X[j]);
upd(i, 1, tmp);
upd(j, 1, -tmp);
}
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= m; ++j)
if (Y[i] > 0 && Y[j] < 0) {
ll tmp = min(Y[i], -Y[j]);
upd(1, i, tmp);
upd(1, j, -tmp);
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
ans += abs(b[i][j]);
printf("%lld\n", ans);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) printf("%lld ", b[i][j]);
printf("\n");
}
return 0;
}
原文地址：http://www.cnblogs.com/Kobe303/p/16876868.html
