当前位置：尊龙游戏旗舰厅官网 > 编程资源 > 编程问答 >内容正文

编程问答

bzoj1202[hnoi2005]狡猾的商人 -尊龙游戏旗舰厅官网

发布时间：2025/1/21 编程问答 7 豆豆

尊龙游戏旗舰厅官网收集整理的这篇文章主要介绍了 bzoj1202[hnoi2005]狡猾的商人小编觉得挺不错的,现在分享给大家,帮大家做个参考.

bzoj1202[hnoi2005]狡猾的商人

题意：

账本上记录了n个月以来的收入情况，其中第i 个月的收入额为ai 。所谓一段时间内的总收入，就是这段时间内每个月的收入额的总和。给出m段时间内的总收入，判断账本是否合法。

题解：

太神了，并查集还能这么用。每月作为一个节点，同时保存父节点表示的月份到该月份的盈利是多少，每次读入一个区间，如果左右端点在同一个集合内，就直接比较两个节点的权值差（因为路径压缩时已经使它们的父节点相同），注意路径压缩时要先递归再维护权值。如果左右端点在不同集合，则合并，设所在子树被合并的那个端点为a2，另一个为a1，a2的根节点为a5，给出的信息为a3，则a5的权值变为w[a5]=w[a1]-w[a2] a3。因为：设a1根节点为a4，s[i]表示i的前缀和，则w[a1]=s[a1]-s[a4] w[a2]=s[a2]-s[a5] a3=s[a2]-s[a1] 显然s[a5]-s[a4]=w[a1]-w[a2] a3=w[a5]。

代码：

1 #include 2 #include 3 #include 4 #define inc(i,j,k) for(int i=j;i<=k;i ) 5 using namespace std; 6 7 int fa[1000],w[1000]; 8 int find(int x){if(x==fa[x])return x;else{int y=find(fa[x]); w[x] =w[fa[x]]; return fa[x]=y;};} 9 int main(){ 10 int t,n,m; scanf("%d",&t); 11 while(t--){ 12 scanf("%d%d",&n,&m); inc(i,0,n)fa[i]=i,w[i]=0; bool f=0; 13 inc(i,1,m){ 14 int a1,a2,a3; scanf("%d%d%d",&a1,&a2,&a3); a1--; 15 int a4=find(a1),a5=find(a2); 16 if(a4==a5&&a3!=w[a2]-w[a1]){printf("false\n");f=1;break;} 17 if(a4!=a5)w[a5]=w[a1]-w[a2] a3,fa[a5]=a4; 18 } 19 if(!f)printf("true\n"); 20 } 21 }

20160401

转载于:https://www.cnblogs.com/yuanziming/p/5693050.html

总结

以上是尊龙游戏旗舰厅官网为你收集整理的bzoj1202[hnoi2005]狡猾的商人的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得尊龙游戏旗舰厅官网网站内容还不错，欢迎将尊龙游戏旗舰厅官网推荐给好友。

上一篇：浏览器的同源限制尊龙游戏旗舰厅官网的解决方案
下一篇：