[PA2014]Fiolki

题目大意：

有\(n(n\le2\times10^5)\)种不同的液体物质和\(n\)个容量无限的药瓶。初始时，第\(i\)个瓶内装着\(g_i\)克第\(i\)种液体。\(m(m\le2\times10^5)\)次操作，第\(i\)个操作是将第\(a_i\)个瓶子内的所有液体倒入第\(b_i\)个瓶子，此后第\(a_i\)个瓶子不会再被用到。

其中，有\(k(k\le5\times10^5)\)对液体物质在一起时会发生反应产生沉淀，具体反应是\(1\)克\(c_i\)物质和\(1\)克\(d_i\)物质生成\(2\)克沉淀，直到某一反应物耗尽。沉淀不会和任何物质反应。当有多于一对可以发生反应的物质在一起时，按照给定的顺序进行。每次会等到反应结束后再执行下一步骤。

求总共产生多少沉淀。

思路：

将容器视作结点，每次操作后的容器视作新的结点，操作前容器向操作后的容器连边，最后形成了一个森林。

找到每次反应的LCA，深度大的反应先发生。因此根据反应的顺序进行模拟即可。

源代码：

#include<cstdio>

#include<cctype>

#include<vector>

#include<algorithm>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

typedef long long int64;

const int N=4e5+1,logN=19,K=5e5;

int tot,g[N],dep[N],anc[N][logN],top[N];

std::vector<int> e[N];

inline void add_edge(const int &u,const int &v) {

	anc[v][0]=u;

	e[u].push_back(v);

}

inline int lg2(const float &x) {

	return ((unsigned&)x>>23&255)-127;

}

void dfs(const int &x,const int &par) {

	dep[x]=dep[par]+1;

	for(register int i=1;i<=lg2(dep[x]);i++) {

		anc[x][i]=anc[anc[x][i-1]][i-1];

	}

	for(unsigned i=0;i<e[x].size();i++) {

		const int &y=e[x][i];

		if(y==par) continue;

		dfs(y,x);

	}

}

inline int lca(int x,int y) {

	if(dep[x]<dep[y]) std::swap(x,y);

	for(register int i=lg2(dep[x]-dep[y]);i>=0;i--) {

		if(dep[anc[x][i]]>=dep[y]) {

			x=anc[x][i];

		}

	}

	for(register int i=lg2(dep[x]);i>=0;i--) {

		if(anc[x][i]!=anc[y][i]) {

			x=anc[x][i];

			y=anc[y][i];

		}

	}

	return x==y?x:anc[x][0];

}

struct Reaction {

	int a,b,d,id;

	bool operator < (const Reaction &rhs) const {

		if(d==rhs.d) return id<rhs.id;

		return d>rhs.d;

	}

};

Reaction r[K];

int main() {

	const int n=tot=getint(),m=getint(),k=getint();

	for(register int i=1;i<=n;i++) {

		g[i]=getint();

		top[i]=i;

	}

	for(register int i=0;i<m;i++) {

		const int u=getint(),v=getint();

		tot++;

		add_edge(tot,top[u]);

		add_edge(tot,top[v]);

		top[v]=tot;

	}

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

		if(!anc[i][0]) dfs(i,0);

	}

	for(register int i=0;i<k;i++) {

		r[i].a=getint();

		r[i].b=getint();

		r[i].d=dep[lca(r[i].a,r[i].b)];

		r[i].id=i;

	}

	std::sort(&r[0],&r[k]);

	int64 ans=0;

	for(register int i=0;i<k;i++) {

		if(!r[i].d) continue;

		const int tmp=std::min(g[r[i].a],g[r[i].b]);

		g[r[i].a]-=tmp;

		g[r[i].b]-=tmp;

		ans+=tmp*2;

	}

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

	return 0;

}

巴特西

[PA2014]Fiolki

[PA2014]Fiolki

题目大意：

思路：

源代码：

最新文章

热门文章