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

Output

Sample Input

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

Sample Output

HINT

Source

鸣谢Jcvb

jesseliu的讲课题，思路和Kruskal重构树的思想比较像。。。

因为每个瓶子倒进一个瓶子之后就废了，那么每个瓶子只有唯一的父亲，那么倾倒操作构成了树结构。。。

然后我们用Peaks类似的方法，把两个瓶子合起来的时候新建一个点表示合并后的瓶子。。。

这样做的好处就是可以维护好每个瓶子内的化学用品还剩多少，因为合并不影响原来瓶子的信息。。。

然后两个反应物相遇的时间就是其Lca的深度，反应的优先级就是序号，

那么我们按照其Lca为第一关键字，反应的优先级为第二关键字排序，然后依次处理反应即可。。。

// MADE BY QT666

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<iostream>

#include<cstring>

using namespace std;

typedef long long ll;

const int N=2000050;

int fa[N],g[N],dfn[N],n,m,k,tt,tot;

int head[N],to[N],nxt[N],cnt;

int size[N],son[N],deep[N],tmp,top[N],father[N];

void lnk(int x,int y){

  to[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt;

  to[++cnt]=x,nxt[cnt]=head[y],head[y]=cnt;

}

void dfs1(int x,int f){

  size[x]=1;deep[x]=deep[f]+1;

  for(int i=head[x];i;i=nxt[i]){

    int y=to[i];if(y==f) continue;

    dfs1(y,x);father[y]=x;size[x]+=size[y];

    if(size[y]>size[son[x]]) son[x]=y;

  }

}

void dfs2(int x,int f){

  top[x]=f;dfn[x]=++tmp;

  if(son[x]) dfs2(son[x],f);

  for(int i=head[x];i;i=nxt[i]){

    int y=to[i];

    if(y==father[x]||y==son[x]) continue;

    dfs2(y,y);

  }

}

int Lca(int x,int y){

  while(top[x]!=top[y]){

    if(deep[top[x]]<deep[top[y]]) swap(x,y);

    x=father[top[x]];

  }

  if(deep[x]<deep[y]) swap(x,y);

  return y;

}

struct data{

  int x,y,Lca,id;

}q[N];

bool cmp(const data &a,const data &b){

  if(deep[a.Lca]==deep[b.Lca]) return a.id<b.id;

  return deep[a.Lca]>deep[b.Lca];

}

int find(int x){

  if(x!=fa[x]) fa[x]=find(fa[x]);

  return fa[x];

}

int main(){

  scanf("%d%d%d",&n,&m,&k);tt=n;

  for(int i=1;i<=n;i++) scanf("%d",&g[i]);

  for(int i=1;i<=n;i++) fa[i]=i;

  for(int i=1;i<=m;i++){

    int x,y;scanf("%d%d",&x,&y);

    tt++;x=find(x),y=find(y);

    lnk(tt,x);lnk(tt,y);fa[x]=fa[y]=tt;fa[tt]=tt;

  }

  for(int i=1;i<=tt;i++) if(find(i)==i) dfs1(i,0),dfs2(i,i);

  for(int i=1;i<=k;i++){

    int x,y;scanf("%d%d",&x,&y);

    if(find(x)==find(y)) q[++tot]=(data){x,y,Lca(x,y),i};

  }

  sort(q+1,q+1+tot,cmp);ll ans=0;

  for(int i=1;i<=tot;i++){

    int res=min(g[q[i].x],g[q[i].y]);

    g[q[i].x]-=res,g[q[i].y]-=res,ans+=1ll*(res<<1);

  }

  printf("%lld\n",ans);

  return 0;

}

巴特西