BZOJ3712[PA2014]Fiolki——并查集重构树-白红宇

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

阅读量：6364 次

发布时间：2019-06-23

本文共 2251 字，大约阅读时间需要 7 分钟。

题目描述

化学家吉丽想要配置一种神奇的药水来拯救世界。

吉丽有n种不同的液体物质，和n个药瓶（均从1到n编号）。初始时，第i个瓶内装着g[i]克的第i种物质。吉丽需要执行一定的步骤来配置药水，第i个步骤是将第a[i]个瓶子内的所有液体倒入第b[i]个瓶子，此后第a[i]个瓶子不会再被用到。瓶子的容量可以视作是无限的。

吉丽知道某几对液体物质在一起时会发生反应产生沉淀，具体反应是1克c[i]物质和1克d[i]物质生成2克沉淀，一直进行直到某一反应物耗尽。生成的沉淀不会和任何物质反应。当有多于一对可以发生反应的物质在一起时，吉丽知道它们的反应顺序。每次倾倒完后，吉丽会等到反应结束后再执行下一步骤。

吉丽想知道配置过程中总共产生多少沉淀。

输入

第一行三个整数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])，按照反应的优先顺序给出。同一个反应不会重复出现。

输出

样例输入

3 2 1

2 3 4

1 2

3 2

2 3

样例输出

我们将每瓶药看成一个节点，对于一个操作合并x,y两瓶药就再新建一个节点代表这个操作，左右子节点分别是x,y两瓶药所在子树的根节点。

这样像kruskal重构树一样建出一棵二叉树，也叫并查集重构树。

可以发现对于每一对反应的两瓶药x,y，都是在它们在并查集重构树上的LCA处那个操作时发生反应的。

我们以每个反应的LCA深度为第一关键字，优先度为第二关键字排序，然后模拟一下即可。

#include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define ll long longusing namespace std;int n,m,k;int g[200010];int fa[400010];int vis[400010];ll ans;int f[400010][20];int d[400010];int cnt;int tot;int ls[400010];int rs[400010];struct miku{ int dep; int pos; int x,y;}a[500010];int x,y;int find(int x){ if(fa[x]==x) { return x; } return fa[x]=find(fa[x]);}bool cmp(miku a,miku b){ if(a.dep!=b.dep) { return a.dep>b.dep; } return a.pos
                 
                  =0;i--) { if(f[x][i]!=f[y][i]) { x=f[x][i]; y=f[y][i]; } } return f[x][0];}int main(){ scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) { scanf("%d",&g[i]); } for(int i=1;i<=2*n;i++) { fa[i]=i; } cnt=n; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); int fx=find(x); int fy=find(y); cnt++; f[fx][0]=cnt; f[fy][0]=cnt; fa[fx]=cnt; fa[fy]=cnt; ls[cnt]=fx; rs[cnt]=fy; } for(int i=1;i<=n;i++) { int rt=find(i); if(!vis[rt]) { vis[rt]=1; dfs(rt); } } for(int i=1;i<=k;i++) { scanf("%d%d",&x,&y); if(find(x)==find(y)) { a[++tot].dep=d[lca(x,y)]; a[tot].pos=i; a[tot].x=x; a[tot].y=y; } } sort(a+1,a+1+tot,cmp); for(int i=1;i<=tot;i++) { int s=g[a[i].x]; int t=g[a[i].y]; if(s>t) { swap(s,t); } ans+=2ll*s; g[a[i].x]-=s; g[a[i].y]-=s; } printf("%lld",ans);}

转载于:https://www.cnblogs.com/Khada-Jhin/p/9789951.html

你可能感兴趣的文章

广州牵引力来告诉你学编程先学什么语言好？