【LCA+并查集】[PA2014]Fiolki

love

[PA2014]Fiolki
时间限制 : 30000 MS   空间限制 : 165536 KB
评测说明 : 2s,128m
问题描述

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

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

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

输入格式

第一行三个整数n,m,k(0<=m<n<=200000,0<=k<=500000)，分别表示药瓶的个数（即物质的种数），操作步数，可以发生的反应数量。

第二行有n个整数g[1],g[2],…,g[n]（1<=g<=10^9)，表示初始时每个瓶内物质的质量。

接下来m行，每行两个整数a,bi，表示第i个步骤。保证a在以后的步骤中不再出现。

接下来k行，每行是一对可以发生反应的物质c,di，按照反应的优先顺序给出。同一个反应不会重复出现。

输出格式

一个整数，表示总共产生多少克沉淀

LCA+并查集

这道题想了很久。
读题，可以知道一个瓶子的物质加入另外一个瓶子后，这个物质所用的瓶子就再也不会出现了。所以这可以构造成一棵树。把这个点的父亲就是它倒入的点。
但是这是不够的（被这个卡了好久）。如果只是这么做的话，没有办法利用点与点之间的深度关系来判断它们反应的先后。
因此有个绝妙的想法。就是它每给一组反应，都新建一个节点，代表他们两两反应后的瓶子。用并查集，这两个点的祖先就指向这个新加的节点。如果后面有新的反应，涉及到了其中的一个节点，则将这个点的祖先与另外那个点的祖先指向一个新加的节点。这样的话，利用每对点的lca的深度，即可以判断他们反应的先后顺序了。

[AppleScript] syntaxhighlighter_viewsource syntaxhighlighter_copycode

#include<stdio.h>
#include<cmath>
#include<iostream>
#include<algorithm>
#define LL long long 
#define N 510001
using namespace std;
struct Node{int d,id,s,e;}P[N];
int n,m,k,cnt;
bool vis[N];
int End[2*N],Last[N],Next[2*N],W[N],F[N][20],D[N],A[N],B[N],C[N],Dd[N],Fa[N];
void add(int x,int y){cnt++;End[cnt]=y;Next[cnt]=Last[x];Last[x]=cnt;}
int GF(int x){return Fa[x]==x?x:Fa[x]=GF(Fa[x]);}
bool cmp(Node x,Node y){
	if(x.d==y.d)return x.id<y.id;
	return x.d>y.d;
}
void DFS(int x){
	vis[x]=1;
	for(int i=1;i<=ceil(log2(D[x]));i++)F[x][i]=F[F[x][i-1]][i-1];
	for(int i=Last[x];i;i=Next[i])D[End[i]]=D[x]+1,F[End[i]][0]=x,DFS(End[i]);
}
int LCA(int x,int y){
	if(D[x]<D[y])swap(x,y);
	int k=D[x]-D[y];
	for(int i=0;i<=ceil(log2(k));i++)if(k&(1<<i))x=F[x][i];
	if(x==y)return x;
	for(int i=18;i>=0;i--)if(F[x][i]!=F[y][i])x=F[x][i],y=F[y][i];
	return F[x][0];
}
int main(){
	int f1,f2,a,b,tot;
	LL ans=0;
	scanf("%d%d%d",&n,&m,&k);
	tot=n;
	for(int i=1;i<=n;i++)scanf("%d",&W[i]),Fa[i]=i;
	for(int i=1;i<=m;i++)scanf("%d%d",&A[i],&B[i]);
	for(int i=1;i<=k;i++)scanf("%d%d",&C[i],&Dd[i]);
	for(int i=1;i<=m;i++){
		f1=GF(A[i]);f2=GF(B[i]);
		++tot;
		add(tot,f1);add(tot,f2);
		Fa[f1]=Fa[f2]=Fa[tot]=tot;
	}
	for(int i=tot;i>=1;i--)if(!vis[i])DFS(i);
	tot=0;
	for(int i=1;i<=k;i++){
		f1=GF(C[i]);f2=GF(Dd[i]);
		if(f1!=f2)continue;
		P[++tot].d=D[LCA(C[i],Dd[i])];
		P[tot].s=C[i];P[tot].e=Dd[i];P[tot].id=tot;
	}
	sort(P+1,P+1+tot,cmp);
	for(int i=1;i<=tot;i++){
		a=min(W[P[i].s],W[P[i].e]);
		ans+=2LL*a;
		W[P[i].s]-=a;W[P[i].e]-=a;
	}
	printf("%lld",ans);
}