比赛 收心赛 评测结果 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;
}