kru重构树求助qwq
查看原帖
kru重构树求助qwq
351272
seashen楼主2022/9/8 16:44
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct edge
{
	int u,v,w;
}e1[500005];
struct EDGE
{
	int v,next;
}e2[1000005];
int head[1000005],idx;
int fa[1000005];
int val[1000005],f[2000005],cnt,vis[1000005];
int top[1000005],son[1000005],siz[1000005],dep[1000005];
int n,m,q;
void add(int u,int v)
{
	e2[++idx].v=v;
	e2[idx].next=head[u];
	head[u]=idx;
}
bool cmp(edge x,edge y)
{
	return x.w>y.w;
}
int find(int u)
{
	if(fa[u]==u) return u;
	return fa[u]=find(fa[u]);
} 
void dfs1(int u,int father,int deep)
{
	int maxson=-1;
	vis[u]=1;f[u]=father;dep[u]=deep;siz[u]=1;
	for(int i=head[u];i;i=e2[i].next)
	{
		int v=e2[i].v;
		if(v==father) continue;
		dfs1(v,u,deep+1);
		siz[u]+=siz[v];
		if(maxson<siz[v]) maxson=siz[v],son[u]=v;
	}
}
void dfs2(int u,int topf)
{
	top[u]=topf;
	if(son[u]) dfs2(son[u],topf);
	for(int i=head[u];i;i=e2[i].next)
	{
		int v=e2[i].v;
		if(v==f[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}
void kruskal()
{
	sort(e1+1,e1+1+m,cmp);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		int fx=find(e1[i].u),fy=find(e1[i].v);
		if(fx!=fy)
		{
			val[++cnt]=e1[i].w;
			fa[cnt]=fa[fx]=fa[fy]=cnt;
			add(fx,cnt);add(cnt,fx);
			add(fy,cnt);add(cnt,fy);
		}
	}
	for(int i=1;i<=cnt;i++)
		if(!vis[i])
		{
			int father=find(i);
			dfs1(father,0,1);
			dfs2(father,father);
		}
	return;
}
int lca(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]>dep[top[y]]) x=fa[top[x]];
		else y=fa[top[y]];
	}
	return dep[x]<dep[y]?x:y;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&e1[i].u,&e1[i].v,&e1[i].w);
	scanf("%d",&q);
	kruskal();
	while(q--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(find(x)!=find(y)) printf("-1\n");
		else printf("%d\n",val[lca(x,y)]);
	}
	return 0;
}

RT 调了一下午了还是没有输出 求大佬给蒟蒻调一下ini

2022/9/8 16:44
加载中...