700字范文,内容丰富有趣,生活中的好帮手!
700字范文 > 【BZOJ5470】[FJOI]所罗门王的宝藏()

【BZOJ5470】[FJOI]所罗门王的宝藏()

时间:2019-05-26 01:38:48

相关推荐

【BZOJ5470】[FJOI]所罗门王的宝藏()

【BZOJ5470】[FJOI]所罗门王的宝藏()

题面

BZOJ

洛谷

有\(n+m\)个变量,给定\(k\)组限制,每次告诉你\(a_i+b_j=c_k\),问是否有可行解。

题解

一道很呆的题目,我都不知道应该算什么类型了。。。

把行列拆开,对于一个限制\(x,y,c\),连边\(x\)行到\(y\)列,边权为\(c\)。

然后\(dfs\)一遍,如果存在环的话显然必须要环上存在合法解,那么随便令一个东西为\(x\),记录每个值为\(ax+b\)的形式,检查二分图是否合法。

#include<iostream>#include<cstdio>using namespace std;#define MAX inline int read(){int x=0;bool t=false;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=true,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return t?-x:x;}int n,m,K;int a[MAX],b[MAX];bool vis[MAX];struct Line{int v,next,w;}e[MAX];int h[MAX],cnt=1;inline void Add(int u,int v,int w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}bool Flag;void dfs(int u){vis[u]=true;if(!Flag)return;for(int i=h[u];i;i=e[i].next){int v=e[i].v,w=e[i].w;if(!vis[v])a[v]=-a[u],b[v]=w-b[u],dfs(v);else if(a[v]+a[u]!=0||b[u]+b[v]!=w){Flag=false;return;}}}int main(){int T=read();while(T--){n=read();m=read();K=read();cnt=1;for(int i=1;i<=K;++i){int x=read(),y=read(),d=read();Add(x,y+n,d);Add(y+n,x,d);}Flag=true;for(int i=1;Flag&&i<=n;++i)if(!vis[i])a[i]=1,b[i]=0,dfs(i);puts(Flag?"Yes":"No");for(int i=1;i<=n+m;++i)vis[i]=false,h[i]=0;}return 0;}

本内容不代表本网观点和政治立场,如有侵犯你的权益请联系我们处理。
网友评论
网友评论仅供其表达个人看法,并不表明网站立场。