P4578 [FJOI]所罗门王的宝藏

传送门

考虑一个位置答案传递性，如果某个位置的红宝石转动确定了，那么会引起连锁反应：

如图，绿色的转动确定了，那么那两个蓝色的转动也确定了

自己手玩一下，发现如果有解那么随便找一个开始然后一路玩下去最后一定会有解，如果一旦有冲突那么之后不管怎么调整也都一定无解，（因为调整最后又会绕回自己继续冲突）

然后就直接BFS搜就好了

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<queue>using namespace std;inline int read(){int x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }return x*f;}const int N=20007;int fir[N],from[N],to[N],val[N],cntt;inline void add(int a,int b,int c){from[++cntt]=fir[a];fir[a]=cntt; to[cntt]=b; val[cntt]=c;}int T,n,m,K;int del[N];bool vis[N],GG;void BFS(int st){queue <int> q;q.push(st); vis[st]=1;while(!q.empty()){int x=q.front(); q.pop();for(int i=fir[x];i;i=from[i]){int &v=to[i],&w=val[i];if(vis[v]){if(del[v]!=w-del[x]) { GG=1; return; }continue;}del[v]=w-del[x]; vis[v]=1;q.push(v);}}}int main(){int a,b,c;T=read();while(T--){memset(vis,0,sizeof(vis)); memset(del,0,sizeof(del));memset(fir,0,sizeof(fir)); cntt=0; GG=0;n=read(); m=read(); K=read();for(int i=1;i<=K;i++){a=read(); b=read(); c=read();add(a,b+n,c); add(b+n,a,c);}for(int i=1;i<=n+m;i++){if(!vis[i]) BFS(i);if(GG) break;}if(GG) printf("No\n");else printf("Yes\n");}return 0;}