UPD 6.12 整体更新
前置：
先转换成图论模型，即每个绿宝石，横坐标向纵坐标连边，权值为绿宝石要的数。
然后就变成了每个点，我按一下可以使得与它相连的边都$+1/-1$，问能否使图边权全部变成$0$。
那么我们顺其自然的开个$del[i]$表示$i$这个点需要删多少次才能符合答案，显然的对于每条边$(u,v,w)$都要有$del[u]+del[v]==w$。
更进一步：
我们思考若原图为一棵树会不会好做些。
求证：对于连边情况为一棵树来说，当一个结点的$del$固定时，有且只有唯一解。
证明：令该节点为根，根层为$0$层，往下为$1$层，$2$层……
由$del[u]+del[v]==w$可知三个值知道两个即可求第三个，所以$0$层的$del$定下来后$1$层的就定了，之后$2$层的就定了……以此类推。
也因此，我们如果对根的$del+k$的话，那么对于每一奇数层$del$就要$-k$，每一偶数层就要$+k$。我们用这一性质可以构造出所有的解。
之后对于非树边，有且只有奇层与偶层的点连边这一种情况。（因为永远都是横纵相连，所以奇奇边和偶偶边是不存在的）
而又因为对于奇数层和偶数层非树边来说两点的$del$和永远不变（一个$+k$一个$-k$抵消了），所以通过它们与边权的比较我们就可以判断答案合法性。
以及我们也因此论证了对于最开始的$del$定什么都无所谓，所以就定$0$呗，何乐而不为呢？
后记：
题解最开始比较意识流，没有详细的证明，所以修正一下。
本人写这个博客时已经是退役一年OIER，因此如果有疏漏请指出。
不过这题作为为数不多自己做出来的省选题果然不算太难，毕竟意识流想法是对的所以反着证明就没有什么难度了……大概？
#include#include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;const int N=2005;inline ll read(){ ll X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct node{ int to,nxt,w;}e[N];int n,m,k,cnt,head[N],del[N];bool vis[N];queue q;inline void add(int u,int v,int w){ e[++cnt].to=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt;}bool bfs(int s){ while(!q.empty())q.pop(); q.push(s);vis[s]=1; while(!q.empty()){ int u=q.front();q.pop(); for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to,w=e[i].w; if(vis[v]){ if(del[u]+del[v]!=w)return 0; }else{ del[v]=w-del[u]; vis[v]=1; q.push(v); } } } return 1;}int main(){ int T=read(); while(T--){ memset(vis,0,sizeof(vis)); memset(head,0,sizeof(head)); cnt=0; n=read(),m=read(),k=read(); for(int i=1;i<=k;i++){ int u=read(),v=read(),w=read(); add(u,v+n,w);add(v+n,u,w); } bool ans=1; for(int i=1;i<=n+m;i++){ if(!vis[i])ans&=bfs(i); } if(ans)puts("Yes"); else puts("No"); } return 0;}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：+
+++++++++++++++++++++++++++++++++++++++++++