重工电子论坛

标题: 【LCA+并查集】[PA2014]Fiolki [打印本页]

---

作者: love    时间: 2018-6-13 00:39
标题: 【LCA+并查集】[PA2014]Fiolki


[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]=F[F[x][i-1]][i-1];

        for(int i=Last[x];i;i=Next)D[End]=D[x]+1,F[End][0]=x,DFS(End);

}

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];

        if(x==y)return x;

        for(int i=18;i>=0;i--)if(F[x]!=F[y])x=F[x],y=F[y];

        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),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[f1]=Fa[f2]=Fa[tot]=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[LCA(C,Dd)];

                P[tot].s=C[tot].e=Dd[tot].id=tot;

        }

        sort(P+1,P+1+tot,cmp);

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

                a=min(W[P.s],W[P.e]);

                ans+=2LL*a;

                W[P.s]-=a;W[P.e]-=a;

        }

        printf("%lld",ans);

}

---

欢迎光临 重工电子论坛 (http://www.cqutlab.cn/)

Powered by Discuz! X3.1