考虑一个位置答案传递性，如果某个位置的红宝石转动确定了，那么会引起连锁反应：
如图，绿色的转动确定了，那么那两个蓝色的转动也确定了
自己手玩一下，发现如果有解那么随便找一个开始然后一路玩下去最后一定会有解，如果一旦有冲突那么之后不管怎么调整也都一定无解，（因为调整最后又会绕回自己继续冲突）
然后就直接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 "); else printf("Yes "); } return 0; }