首页 > 代码库 > bzoj 3712: [PA2014]Fiolki
bzoj 3712: [PA2014]Fiolki
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])，按照反应的优先顺序给出。同一个反应不会重复出现。
操作的过程可以看做一棵二叉树/森林，叶节点为药瓶，其余节点对应于操作，求lca可以找出一个反应发生的那次操作，然后在树上dfs一次模拟求出答案
#include<cstdio>char buf[16000000],*ptr=buf-1;const int N=200007;int _(){ int x=0,c=*++ptr; while(c<48)c=*++ptr; while(c>47)x=x*10+c-48,c=*++ptr; return x;}int n,m,k,g[N];int ch[N*2][2],fa[N*2],son[N*2],sz[N*2],dep[N*2],top[N*2],f[N*2],idp,v[500007][2];int es[500007],enx[500007],e0[500007],ep=2;long long ans=0;bool ed[N*2];void f1(int w,int pa){ dep[w]=dep[fa[w]=pa]+1; sz[w]=1; if(w>n) for(int i=0;i<2;++i){ int u=ch[w][i]; f1(u,w); sz[w]+=sz[u]; if(sz[u]>sz[son[w]])son[w]=u; }}void f2(int w,int tp){ top[w]=tp; if(son[w])f2(son[w],tp); if(w>n) for(int i=0;i<2;++i){ int u=ch[w][i]; if(u!=son[w])f2(u,u); }}int min(int a,int b){return a<b?a:b;}void dec(int w){ int x=v[w][0],y=v[w][1],z=min(g[x],g[y]); g[x]-=z,g[y]-=z,ans+=z;}void f3(int w){ if(w>n) for(int i=0;i<2;++i)f3(ch[w][i]); for(int i=e0[w];i;i=enx[i])dec(es[i]);}int lca(int x,int y){ int a=top[x],b=top[y]; while(a!=b){ if(dep[a]>dep[b])x=fa[a],a=top[x]; else y=fa[b],b=top[y]; } return dep[x]<dep[y]?x:y;}int get(int x){ int a=x,c; while(x!=f[x])x=f[x]; while(x!=f[a])c=f[a],f[a]=x,a=c; return x;}int main(){ fread(buf,1,sizeof(buf),stdin); idp=n=_();m=_();k=_(); for(int i=1;i<=n;++i)g[i]=_(),f[i]=i; for(int i=1,a,b;i<=m;++i){ a=_(),b=_(); ++idp; a=get(a),b=get(b); ch[idp][0]=a; ch[idp][1]=b; ed[a]=ed[b]=1; f[a]=f[b]=f[idp]=idp; } for(int i=1;i<=idp;++i)if(!ed[i])f1(i,0),f2(i,i); for(int i=1;i<=k;++i)v[i][0]=_(),v[i][1]=_(); for(int i=k;i;--i){ int c=lca(v[i][0],v[i][1]); if(c)es[ep]=i,enx[ep]=e0[c],e0[c]=ep++; } for(int i=1;i<=idp;++i)if(!ed[i])f3(i); printf("%lld\n",ans<<1); return 0;}
bzoj 3712: [PA2014]Fiolki
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。