洛谷4578 & LOJ2520:[FJOI2018]所罗门王的宝藏——题解

时间:2023-03-08 16:26:24
洛谷4578 & LOJ2520:[FJOI2018]所罗门王的宝藏——题解

https://www.luogu.org/problemnew/show/P4578

https://loj.ac/problem/2520

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<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=;
inline ll read(){
ll X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),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<int>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]=;
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 ;
}else{
del[v]=w-del[u];
vis[v]=;
q.push(v);
}
}
}
return ;
}
int main(){
int T=read();
while(T--){
memset(vis,,sizeof(vis));
memset(head,,sizeof(head));
cnt=;
n=read(),m=read(),k=read();
for(int i=;i<=k;i++){
int u=read(),v=read(),w=read();
add(u,v+n,w);add(v+n,u,w);
}
bool ans=;
for(int i=;i<=n+m;i++){
if(!vis[i])ans&=bfs(i);
}
if(ans)puts("Yes");
else puts("No");
}
return ;
}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者:luyouqi233。               +

+欢迎访问我的博客:http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++