[杂题]「FJOI2018」所罗门王的宝藏

题目大意

给出一个(n)*(m)的空矩阵,每次可以使任意一行/列(+1/-1),给出(k)个位置的最终结果,询问是否存在解.

(1<=n,m,k<=1000)

解题思路

考虑把每一行/列看成点,限制看成边权,操作就是把与某个点相连的所有边(+1/-1),询问能否使边权都变为(0).

我们显然只需要考虑环上的情况,随便设环上某个点的值为(x),其他点都可以表示成(ax+b)的形式,考虑最后的一条环边是否满足即可.

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=2005;
int tot,lnk[maxn],nxt[2*maxn],son[2*maxn],w[2*maxn];
int T,n,m,K,pd,a[maxn],b[maxn];
bool vis[maxn];
void add(int x,int y,int z){nxt[++tot]=lnk[x];lnk[x]=tot;son[tot]=y;w[tot]=z;}
void DFS(int x){
	vis[x]=1;
	for (int j=lnk[x];j;j=nxt[j]){
		if (!vis[son[j]]) a[son[j]]=-a[x],b[son[j]]=w[j]-b[x],DFS(son[j]);
		else if (a[son[j]]+a[x]!=0||b[x]+b[son[j]]!=w[j]) pd=0;
	}
}
int main(){
	freopen("exam.in","r",stdin);
	freopen("exam.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&n,&m,&K),tot=0;
		memset(lnk,0,sizeof(lnk));
		while(K--){
			int x,y,z;scanf("%d%d%d",&x,&y,&z);
			add(x,y+n,z);add(y+n,x,z);
		}
		memset(vis,0,sizeof(vis));pd=1;
		for (int i=1;i<=n;i++) if (!vis[i]) a[i]=1,DFS(i);
		if (pd) printf("Yes
");else printf("No
");
	}
	return 0;
}