【BZOJ3712】Fiolki（并查集重构树）

题面

题解

很神仙的题目。

我们发现所有的合并关系构成了一棵树。

那么两种不同的东西如果产生反应，一定在两个联通块恰好联通的时候反应。

那么，我们按照并查集的合并顺序，类似于克鲁斯卡尔重构树的方法构建一个并查集重构树，

发现所有的反应恰好在两者的\(LCA\)处发生，

所以把所有可以发生的翻译拿出来，

按照\(LCA\)的深度为第一关键字，反应的优先级为第二关键字排序。

然后按顺序依次计算答案就好了。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define ll long long

#define RG register

#define MAX 500500

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

ll ans;

int n,m,g[MAX],k;

struct Line{int v,next;}e[MAX];

int h[MAX],cnt=1;

inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}

int size[MAX],hson[MAX],top[MAX],fa[MAX],dep[MAX];

void dfs1(int u,int ff)

{

	dep[u]=dep[ff]+1;fa[u]=ff;size[u]=1;

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;if(v==ff)continue;

		dfs1(v,u);size[u]+=size[v];

		if(size[v]>size[hson[u]])hson[u]=v;

	}

}

void dfs2(int u,int tp)

{

	top[u]=tp;

	if(hson[u])dfs2(hson[u],tp);

	for(int i=h[u];i;i=e[i].next)

		if(e[i].v!=hson[u]&&e[i].v!=fa[u])

			dfs2(e[i].v,e[i].v);

}

int LCA(int u,int v)

{

	while(top[u]^top[v])dep[top[u]]<dep[top[v]]?v=fa[top[v]]:u=fa[top[u]];

	return dep[u]<dep[v]?u:v;

}

int f[MAX],tot;

struct Event{int dep,id,u,v;}p[MAX];

bool operator<(Event a,Event b)

{

	if(a.dep!=b.dep)return a.dep>b.dep;

	return a.id<b.id;

}

int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}

int main()

{

	n=read();m=read();k=read();

	for(int i=1;i<=n;++i)g[i]=read(),f[i]=i;

	for(int i=1;i<=m;++i)

	{

		int a=read(),b=read();

		Add(n+i,f[getf(a)]);Add(n+i,f[getf(b)]);

		f[getf(a)]=f[getf(b)]=n+i;f[n+i]=n+i;

	}

	for(int i=n+m;i;--i)if(!dep[i])dfs1(i,0),dfs2(i,i);

	for(int i=1;i<=k;++i)

	{

		int u=read(),v=read();

		if(getf(u)!=getf(v))continue;

		int s=LCA(u,v);

		p[++tot]=(Event){dep[s],i,u,v};

	}

	sort(&p[1],&p[tot+1]);

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

	{

		int u=p[i].u,v=p[i].v;

		int s=min(g[u],g[v]);

		ans+=s;g[u]-=s;g[v]-=s;

	}

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

}

巴特西

【BZOJ3712】Fiolki（并查集重构树）

【BZOJ3712】Fiolki（并查集重构树）

题面

题解

最新文章

热门文章