lp4578 FJOI2018 所罗门王的宝藏

首先,我们可以知道,令每一行、列数字的变化为\(dx_{i},dy_{i}\),那么对于\(z_{i,j}\),一定有:
$$dx_{i}+dy_{j}=z_{i,j}$$
对这个线性方程组变形,我们可以发现,如果指定序列合法,那么:
$$ \forall x ,z_{x,j_{1}}-z_{x,j_{2}}=dy_{j_{1}}-dy_{j_{2}} $$
$$ \forall y ,z_{i_{1},y}-z_{i_{2},y}=dx_{i_{1}}-dx_{i_{2}} $$
而,当\(dx\)和\(dy\)的相对关系不矛盾时,一定可以导出一个符合题意的矩阵。
因此,我们对于每组\(x,y\),统计它们的相对关系即可。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,k; 
int dx[1005][1005],dy[1005][1005];
bool visx[1005][1005],visy[1005][1005];
int x[1005],y[1005],z[1005];
void init(){
    memset(dx,0,sizeof(dx));
    memset(dy,0,sizeof(dy));
    memset(visx,0,sizeof(visx));
    memset(visy,0,sizeof(visy));
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;++i){
        scanf("%d%d%d",&x[i],&y[i],&z[i]);
    }
    int nw;
    for(int i=1;i<k;++i){
        for(int j=i+1;j<=k;++j){
            if(x[i]==x[j]&&y[i]==y[j]&&z[i]!=z[j]){
                puts("No");
                return; 
            }
            if(x[i]==x[j]){
                nw=y[i]>y[j]?z[j]-z[i]:z[i]-z[j];
                if(visx[y[i]][y[j]]&&dx[y[i]][y[j]]!=nw){
                    puts("No");
                    return;
                }
                dx[y[i]][y[j]]=dx[y[j]][y[i]]=nw;
                visx[y[i]][y[j]]=visx[y[j]][y[i]]=1; 
            }
            if(y[i]==y[j]){
                nw=x[i]>x[j]?z[j]-z[i]:z[i]-z[j];
                if(visy[x[i]][x[j]]&&dy[x[i]][x[j]]!=nw){
                    puts("No");
                    return;
                }
                dy[x[i]][x[j]]=dy[x[j]][x[i]]=nw;
                visy[x[i]][x[j]]=visy[x[j]][x[i]]=1; 
            }
        }
    }
    for(int i=1;i<=n;++i){
        if(dx[i][i]||dy[i][i]){
            puts("No");
            return;
        }
    }
    puts("Yes");
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}