关于倍增LCA
查看原帖
关于倍增LCA
137723
pencil楼主2021/10/21 13:33
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
struct oi{
	int a,b,c;
};
oi a[100010];
int f[100010][30],z[100010],ne[100010],v[1000010],h[1000010],idx=0,d[100010],sm[100010],fa[100011];
bool cmp(oi a,oi b) {
	return a.c>b.c;
}
int find(int x){
	if(fa[x]!=x)
	fa[x]=find(fa[x]);
	return fa[x]; 
}
void add(int a,int b,int c){
	ne[++idx]=h[a];
	z[idx]=b;
	h[a]=idx;
	v[idx]=c;
}
int lca(int tt,int ntt){
	if(d[tt]>d[ntt])
	swap(tt,ntt);
	int i;
	for(i=20;i>=0;i--){
		int fy=f[ntt][i];
		if(d[fy]>=d[tt]&&fy!=0)
		ntt=fy;
	}
	for(i=20;i>=0;i--){
		int fx=f[tt][i],fy=f[ntt][i];
		if(fx!=fy&&fx>0&&fy>0){
			tt=fx;
			ntt=fy;
		}
	}
	if(tt==ntt)//||
	return sm[tt];
	else
	if(f[tt][0]==f[ntt][0])
	return sm[f[tt][0]];
	else
	return -1;
}
void dfs(int root,int depth,int last,int inf){
	d[root]=depth;
	sm[root]=inf;
//	sm[root]=a[root].c;
	for(int i=h[root];i;i=ne[i]){
		if(z[i]!=last){
			dfs(z[i],depth+1,root,v[i]);
//			sm[]
			sm[root]=min(sm[root],sm[z[i]]);
			f[z[i]][0]=root;
		}
		
	}
}
int main(){
	int n,m,i,op;
	cin>>n>>m;
	for(i=1;i<=m;i++){
		cin>>a[i].a>>a[i].b>>a[i].c;
	}
	sort(a+1,a+1+m,cmp);
	for(i=1;i<=n;i++)
	fa[i]=i;
	for(i=1;i<=m;i++){
		int k=a[i].a,z=a[i].b,fk=find(k),fz=find(z);
		if(fk!=fz){
			add(k,z,a[i].c);
			add(z,k,a[i].c);
			fa[fk]=fz;
//			sm[k]=min(sm[k],a[i],c) 
		}
	}
	memset(d,0x3f,sizeof(d));memset(sm,0x3f,sizeof(sm));
	dfs(1,1,0,0x3f3f3f3f);
	int i2;
	for(i=1;i<=20;i++){
		for(i2=1;i2<=n;i2++){
			f[i2][i]=f[f[i2][i-1]][i-1];
		}
	}
	cin>>op;
	for(i=1;i<=op;i++){
		int c1,c2;
		cin>>c1>>c2;
		cout<<lca(c1,c2)<<endl; 
	}
	return 0;
}

这样写哪里错了呢。。。

2021/10/21 13:33
加载中...