重工电子论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
热搜: 活动 交友 discuz
查看: 137|回复: 0

[其他] 【LCA+并查集】[PA2014]Fiolki

[复制链接]

6

主题

6

帖子

26

积分

新手上路

Rank: 1

积分
26
发表于 2018-6-13 00:39:15 | 显示全部楼层 |阅读模式
本帖最后由 love 于 2018-6-21 18:46 编辑

[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);
}

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|cqutlab ( 渝ICP备15004556号

GMT+8, 2018-11-15 12:17 , Processed in 0.112259 second(s), 28 queries .

Powered by Discuz! X3.1

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表