【LCA+并查集】[PA2014]Fiolki
本帖最后由 love 于 2018-6-21 18:46 编辑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,g,…,g（1<=g<=10^9)，表示初始时每个瓶内物质的质量。
接下来m行，每行两个整数a,bi，表示第i个步骤。保证a在以后的步骤中不再出现。
接下来k行，每行是一对可以发生反应的物质c,di，按照反应的优先顺序给出。同一个反应不会重复出现。
输出格式
一个整数，表示总共产生多少克沉淀
LCA+并查集
这道题想了很久。
读题，可以知道一个瓶子的物质加入另外一个瓶子后，这个物质所用的瓶子就再也不会出现了。所以这可以构造成一棵树。把这个点的父亲就是它倒入的点。
但是这是不够的（被这个卡了好久）。如果只是这么做的话，没有办法利用点与点之间的深度关系来判断它们反应的先后。
因此有个绝妙的想法。就是它每给一组反应，都新建一个节点，代表他们两两反应后的瓶子。用并查集，这两个点的祖先就指向这个新加的节点。如果后面有新的反应，涉及到了其中的一个节点，则将这个点的祖先与另外那个点的祖先指向一个新加的节点。这样的话，利用每对点的lca的深度，即可以判断他们反应的先后顺序了。
#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;
int n,m,k,cnt;
bool vis;
int End,Last,Next,W,F,D,A,B,C,Dd,Fa;
void add(int x,int y){cnt++;End=y;Next=Last;Last=cnt;}
int GF(int x){return Fa==x?x:Fa=GF(Fa);}
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=1;
for(int i=1;i<=ceil(log2(D));i++)F=F];
for(int i=Last;i;i=Next)D]=D+1,F]=x,DFS(End);
}
int LCA(int x,int y){
if(D<D)swap(x,y);
int k=D-D;
for(int i=0;i<=ceil(log2(k));i++)if(k&(1<<i))x=F;
if(x==y)return x;
for(int i=18;i>=0;i--)if(F!=F)x=F,y=F;
return F;
}
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),Fa=i;
for(int i=1;i<=m;i++)scanf("%d%d",&A,&B);
for(int i=1;i<=k;i++)scanf("%d%d",&C,&Dd);
for(int i=1;i<=m;i++){
f1=GF(A);f2=GF(B);
++tot;
add(tot,f1);add(tot,f2);
Fa=Fa=Fa=tot;
}
for(int i=tot;i>=1;i--)if(!vis)DFS(i);
tot=0;
for(int i=1;i<=k;i++){
f1=GF(C);f2=GF(Dd);
if(f1!=f2)continue;
P[++tot].d=D,Dd)];
P.s=C;P.e=Dd;P.id=tot;
}
sort(P+1,P+1+tot,cmp);
for(int i=1;i<=tot;i++){
a=min(W.s],W.e]);
ans+=2LL*a;
W.s]-=a;W.e]-=a;
}
printf("%lld",ans);
}
页:
[1]