题目大意
给你一个 \(n\times n\) 的数组 \(C\)，\(c_{i,j}=a_i+b_j\)，求 \(a\) 数组与 \(b\) 数组，不保证有解，其中 \(1\le n\le 500,1\le c_{i,j}\le 10^9\)，而且 \(a_i,b_i\) 都是非负整数。
\[\begin{bmatrix} a_1+b_1&a_1+b_2&\cdots&a_1+b_{n-1}&a_1+b_n\\ a_2+b_1&a_2+b_2&\cdots&a_2+b_{n-1}&a_2+b_n\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ a_{n-1}+b_1&a_{n-1}+b_2&\cdots&a_{n-1}+b_{n-1}&a_{n-1}+b_n\\ a_n+b_1&a_n+b_2&\cdots&a_n+b_{n-1}&a_n+b_n\\ \end{bmatrix}\]思路
因为 \(c_{i,j}=a_i+b_j,c_{i,j+1}=a_i+b_{j+1}\)。
所以 \(c_{i,j}-c_{i,j+1}=a_i+b_j-(a_i+b_{j+1})=a_j-a_{j+1}\)。
将我们一行依次相减，就得到了 \(b\) 的一组关系，其实就是 \(n-1\) 个等式。
\(\begin{cases} b_1-b_2=c_{i,1}-c_{i,2}\\ \cdots\\ b_{n-1}-b_{n}=c_{i,n-1}-c_{i,n} \end{cases}\)
显然，对于所有的 \(i\in [1,n]\) 这 \(n-1\) 个等式应该都是满足的。如果不能满足这个条件，那么就是无解的。
因为 \(a_i,b_i\) 都是非负整数，所以我们需要找到一组解使上面的等式全部满足。为了让答案在最后好处理，我们可以先找到一组最小解。
因为上面的方程对于所有的 \(i\in [1,n]\) 都满足，所以我们只需要考虑一行就可以了，为了便于讨论，我选取了第 \(1\) 行。得到第 \(i\) 行最小的元素 \(x\)，所有 \(b_i=a_i-x\)，对于 \(a\) 数组也是如此。
因为我们找到的是最小解，所有有可能会出现 \(a_i+b_j<c_{i,j}\) 的情况。因为我们已经得到了 \(a\) 数组之间的关系，那么我们就可以将 \(a\) 数组全部加 \(1\)。
AC Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=505;
int n,c[N][N],a[N],b[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>c[i][j];
}
}
for(int i=1;i<n;i++){
for(int j=1;j<n;j++){
if(c[i][j]-c[i][j+1]!=c[i+1][j]-c[i+1][j+1]){
cout<<"No";
return 0;
}
}
}
for(int j=1;j<n;j++){
for(int i=1;i<n;i++){
if(c[i][j]-c[i][j+1]!=c[i+1][j]-c[i+1][j+1]){
cout<<"No";
return 0;
}
}
}
int mmin=INT_MAX;
for(int i=1;i<=n;i++){
mmin=min(c[1][i],mmin);
}
for(int i=1;i<=n;i++){
b[i]=c[1][i]-mmin;
}
mmin=INT_MAX;
for(int i=1;i<=n;i++){
mmin=min(c[i][1],mmin);
}
for(int i=1;i<=n;i++){
a[i]=c[i][1]-mmin;
}
cout<<"Yes\n";
int add=c[1][1]-a[1]-b[1];
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
cout<<'\n';
for(int i=1;i<=n;i++){
cout<<b[i]+add<<" ";
}
return 0;
}