BZOJ3712 [PA2014]Fiolki 重构树+并查集

发布于 2017-09-03  4.42k 次阅读


[toggle hide="yes" title="题目" color=""]

Description

化学家吉丽想要配置一种神奇的药水来拯救世界。
吉丽有n种不同的液体物质,和n个药瓶(均从1到n编号)。初始时,第i个瓶内装着g[i]克的第i种物质。吉丽需要执行一定的步骤来配置药水,第i个步骤是将第a[i]个瓶子内的所有液体倒入第b[i]个瓶子,此后第a[i]个瓶子不会再被用到。瓶子的容量可以视作是无限的。
吉丽知道某几对液体物质在一起时会发生反应产生沉淀,具体反应是1克c[i]物质和1克d[i]物质生成2克沉淀,一直进行直到某一反应物耗尽。生成的沉淀不会和任何物质反应。当有多于一对可以发生反应的物质在一起时,吉丽知道它们的反应顺序。每次倾倒完后,吉丽会等到反应结束后再执行下一步骤。
吉丽想知道配置过程中总共产生多少沉淀。

Input

第一行三个整数n,m,k(0<=m<n<=200000,0<=k<=500000),分别表示药瓶的个数(即物质的种数),操作步数,可以发生的反应数量。
第二行有n个整数g[1],g[2],…,g[n](1<=g[i]<=10^9),表示初始时每个瓶内物质的质量。
接下来m行,每行两个整数a[i],b[i](1<=a[i],b[i]<=n,a[i]≠b[i]),表示第i个步骤。保证a[i]在以后的步骤中不再出现。
接下来k行,每行是一对可以发生反应的物质c[i],d[i](1<=c[i],d[i]<=n,c[i]≠d[i]),按照反应的优先顺序给出。同一个反应不会重复出现。

Sample Input

3 2 1
2 3 4
1 2
3 2
2 3

Sample Output

6

[/toggle]

又是一道思路非常好的题目。考虑到每个反应最多只进行一次,每个瓶子也只能往外倒一次,我们可以把每个瓶子想成一棵树。初始时,所有节点都是根节点,构成森林,每操作一次,就将两个瓶子表示的节点合并起来,可以用并查集维护,合并后的点重新标号,成为原来两个点的父节点,从下往上建树。注意到当两个物质能发生反应时,一定是在重新构建的树的LCA上进行,而又因为每个节点都是按照反应的顺序建出来的,所以枚举每个反应并将反应挂到两个物质的LCA上,当访问到LCA时,如果还有物质剩余,则可以反应。显然在最后从小到大枚举每个节点,暴力模拟反应的过程即可。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974