BZOJ1202狡猾的商人[并查集]

这是一道作死的题。这是一道拉低胜率的题。

大概思路就是并查集。

首先根据题目我们可以分析一下,如果这个账本是真的话,那么对于一个s,t,在图上,两个点之间任意一条路径的长度都必须相等,不然这个账本就不是真的。

用并查集在维护这个信息,也就是前缀和,前缀和就是前i个月收入的钱,那么对于任意一行数据  s  t  v   都有 sum[s] - sum[t] = v

然后在并查集的时候,查找父亲节点的时候,将sum值累加起来。

然后再读入的时候进行一下判断就可以了

如果对于 fa[s] != fa[t],那么先合并这2个点,然后sum[fa[x]] = sum[t] - sum[s] + v; 

这个很好理解。。

于是就这样。。

原文地址:https://www.cnblogs.com/lalawu/p/3558644.html