划年代久远的水
有一个R*C的棋盘,要求在每个格子上填一个非负数,使得对任意一个2*2的正方形区域,左上角和右下角的数字之和等于左下角和右上角的数字之和.有一些格子已经被填上了数字,问现在能否满足要求,输出Yes或No. R,C<=1e5,已经被填上数字的格子数<=1e5
记i行j列的数字为num[i][j] 假设一个2*2的正方形区域中,左上角,右上角,左下角,右下角依次为a,b,c,d,那么a+d=b+c,也就是说,a-b=c-d,a-c=b-d. 由此我们可以推出这样的结论: 对于任意不同的两行a和b,它们第i列和第j列的数字之差是相同的.即num[a][i]-num[a][j]=num[b][i]-num[b][j] 对于任意不同的两列a和b,它们第i行和第j行的数字之差是相同的.即num[i][a]-num[j][a]=num[i][b]-num[j][b] 于是我们可以用两个带权并查集,分别维护列之间数字之差和行之间数字之差.如果数字之差出现矛盾则无解.同时推出由已知的条件能确定的数值最小的数字,如果这个数字是负数则无解.否则有解.
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define GG return puts("No"),0; const int maxn=100005; typedef long long ll; int ufs1[maxn];ll w1[maxn]; int ufs2[maxn];ll w2[maxn]; struct node{ int x,y,val; void read(){ scanf("%d%d%d",&x,&y,&val); } }P[maxn]; bool cmpx(const node &A,const node &B){ return A.x<B.x; } bool cmpy(const node &A,const node &B){ return A.y<B.y; } int find1(int x){ if(x==ufs1[x])return x; int rt=find1(ufs1[x]); w1[x]+=w1[ufs1[x]]; return ufs1[x]=rt; } int find2(int x){ if(x==ufs2[x])return x; int rt=find2(ufs2[x]); w2[x]+=w2[ufs2[x]]; return ufs2[x]=rt; } bool link1(int a,int b,ll w){ if(find1(a)!=find1(b)){ int ra=find1(a),rb=find1(b); ufs1[ra]=ufs1[rb]; w1[ra]=w+w1[b]-w1[a]; return true; }else{ return w1[a]==w+w1[b]; } } bool link2(int a,int b,ll w){ if(find2(a)!=find2(b)){ int ra=find2(a),rb=find2(b); ufs2[ra]=ufs2[rb]; w2[ra]=w+w2[b]-w2[a]; return true; }else{ return w2[a]==w+w2[b]; } } ll Min1[maxn],Min2[maxn]; int main(){ int R,C;scanf("%d%d",&R,&C); for(int i=1;i<=R;++i){ ufs1[i]=i;w1[i]=0; } for(int i=1;i<=C;++i){ ufs2[i]=i;w2[i]=0; } int n;scanf("%d",&n); for(int i=1;i<=n;++i)P[i].read(); sort(P+1,P+n+1,cmpx); for(int i=1;i<n;++i){ if(P[i].x==P[i+1].x){ if(!link2(P[i].y,P[i+1].y,P[i+1].val-P[i].val))GG; } } sort(P+1,P+n+1,cmpy); for(int i=1;i<n;++i){ if(P[i].y==P[i+1].y){ if(!link1(P[i].x,P[i+1].x,P[i+1].val-P[i].val))GG; } } memset(Min1,0x3f,sizeof(Min1)); memset(Min2,0x3f,sizeof(Min2)); for(int i=1;i<=n;++i){ int rt=find1(P[i].x); Min1[rt]=min(Min1[rt],P[i].val+w1[P[i].x]); } for(int i=1;i<=R;++i){ int rt=find1(i); Min2[rt]=min(Min2[rt],-w1[i]); } for(int i=1;i<=R;++i){ if(ufs1[i]==i&&Min1[i]+Min2[i]<0){ GG; } } memset(Min1,0x3f,sizeof(Min1)); memset(Min2,0x3f,sizeof(Min2)); for(int i=1;i<=n;++i){ int rt=find2(P[i].y); Min1[rt]=min(Min1[rt],P[i].val+w2[P[i].y]); } for(int i=1;i<=C;++i){ int rt=find2(i); Min2[rt]=min(Min2[rt],-w2[i]); } for(int i=1;i<=C;++i){ if(ufs2[i]==i&&Min1[i]+Min2[i]<0)GG; } printf("Yes\n"); return 0; }转载于:https://www.cnblogs.com/liu-runda/p/7116594.html
相关资源：数据结构—成绩单生成器