| 比赛 |
收心赛 |
评测结果 |
WWWWWWWAAAWWWWWTTTTT |
| 题目名称 |
矩阵游戏 |
最终得分 |
15 |
| 用户昵称 |
赵飞羽 |
运行时间 |
6.749 s |
| 代码语言 |
C++ |
内存使用 |
10.44 MiB |
| 提交时间 |
2026-02-24 10:39:24 |
显示代码纯文本
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 310, M = 200010;
int T, n, m, a[N][N], b[N][N], c[N][N];
int hd[N*2], ver[M], pre[M], val[M], idx;
int s = 0, dis[N*2], vis[N*2], cnt[N*2];
void add(int x, int y, int w) {
ver[++idx] = y;
val[idx] = w;
pre[idx] = hd[x];
hd[x] = idx;
}
int SPFA() {
queue <int> q;
q.push(s);
while (!q.empty()) {
int x = q.front();
q.pop();
vis[x] = 0;
for (int i = hd[x]; i; i = pre[i]) {
int y = ver[i];
if (dis[x] >= 0x3f3f3f3f) continue;
if (dis[y] > dis[x] + val[i]) {
dis[y] = dis[x] + val[i];
if (!vis[y]) {
cnt[y] = cnt[x] + 1;
if (cnt[y] > n + 1) return 1;
q.push(y);
vis[y] = 1;
}
}
}
}
return 0;
}
signed main() {
freopen("matrix.in", "r", stdin);
freopen("matrix.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> T;
while (T--) {
cin >> n >> m;
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
memset(cnt, 0, sizeof(cnt));
memset(hd, 0, sizeof(hd));
memset(ver, 0, sizeof(ver));
memset(pre, 0, sizeof(pre));
memset(val, 0, sizeof(val));
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(c, 0, sizeof(c));
idx = 0;
s = 0;
dis[s] = 0;
vis[s] = 1;
for (int i = 1; i <= n + m; i++) add(0, i, 0);
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
cin >> b[i][j];
}
}
for (int i = n - 1; i >= 1; i--) {
for (int j = n - 1; j >= 1; j--) {
c[i][j] = b[i][j] - c[i+1][j] - c[i][j+1] - c[i+1][j+1];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int x = ((i % 2 && j % 2)? i: j + n);
int y = (x == j + n? i: j + n);
add(x, y, 1000000 - c[i][j]);
add(y, x, c[i][j]);
}
}
if (SPFA()) cout << "NO\n";
else {
cout << "YES\n";
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
a[i][j] = c[i][j] + dis[i] * ((i + j) % 2? 1: -1) + dis[j+n] * ((i + j) % 2? -1: 1);
cout << a[i][j] << " ";
}
cout << "\n";
}
}
}
return 0;
}